Shortest paths anonymization on weighted graphs

Shyue Liang Wang, Yu Chuan Tsai, Hung Yu Kao, I. Hsien Ting, Tzung Pei Hong

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Due to the proliferation of online social networking, a large number of personal data are publicly available. As such, personal attacks, reputational, financial, or family losses might occur once this personal and sensitive information falls into the hands of malicious hackers. Research on Privacy-Preserving Network Publishing has attracted much attention in recent years. But most work focus on node de-identification and link protection. In academic social networks, business transaction networks, and transportation networks, etc, node identities and link structures are public knowledge but weights and shortest paths are sensitive. In this work, we study the problem of k-anonymous path privacy. A published network graph with k-anonymous path privacy has at least k indistinguishable shortest paths between the source and destination vertices [21]. In order to achieve such privacy, three different strategies of modification on edge weights of directed graphs are proposed. Numerical comparisons show that weight-proportional-based strategy is more efficient than PageRank-based and degree-based strategies. In addition, it is also more efficient and causes less information loss than running on un-directed graphs.

Original languageEnglish
Pages (from-to)65-79
Number of pages15
JournalInternational Journal of Software Engineering and Knowledge Engineering
Issue number1
Publication statusPublished - 2013 Feb

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Shortest paths anonymization on weighted graphs'. Together they form a unique fingerprint.

Cite this