Featured Topic Issue: Semantic Methods for Knowledge Management; Guest Editors: J. J. Jung, R. P. Katarzyniak and N. T. NguyenNo Access

SHORTEST PATHS ANONYMIZATION ON WEIGHTED GRAPHS

SHYUE-LIANG WANG

Department of Information Management, National University of Kaohsiung, Kaohsiung, Taiwan 81148, Taiwan

Search for more papers by this author

YU-CHUAN TSAI

Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan 70101, Taiwan

Search for more papers by this author

HUNG-YU KAO

Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan 70101, Taiwan

Search for more papers by this author

I-HSIEN TING

Department of Information Management, National University of Kaohsiung, Kaohsiung, Taiwan 81148, Taiwan

Search for more papers by this author

, and

TZUNG-PEI HONG

Department of Computer Science and Information Engineering, National University of Kaohsiung, Kaohsiung, Taiwan 81148, Taiwan

Search for more papers by this author

https://doi.org/10.1142/S0218194013400056Cited by:7 (Source: Crossref)

Abstract

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.

Note: Part of this work has been presented at ACIIDS 2011.

Keywords:

References

L. Backstromet al., Group formation in large social networks: membership, growth, and evolution, Proc. KDD (2006) pp. 44–54. Google Scholar
L. Backstrom, C. Dwork and J. M. Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proc. WWW (2007) pp. 181–190. Google Scholar
D. Banisar, Freedom of Information around the World 2006 — A Global Survey of Access to Government Information Laws, www.privacyinternational.org/foi/survey . Google Scholar
M. Barbaro and T. Z. Jr, A face is exposed for AOL searcher no. 4417749, New York Times, Aug. 2006 . Google Scholar
J. Cheng, A. Fu and J. Liu, K-isomorphism: privacy preserving network publication against structural attacks, Proc. SIGMOD Conference (2010) pp. 459–470. Google Scholar
S. Das, O. Egecioglu and A. E. Abbadi, Anonymizing weighted social network graphs, Proc. ICDE (2010) pp. 904–907. Google Scholar
Jun Gao et al. , Neighborhood-Privacy Protected Shortest Distance Computing in Cloud , Proc. SIGMOD ( 2011 ) . Google Scholar
M. Hayet al., Resisting structural re-identification in anonymized social networks, Proc. PVLDB1 (2008) pp. 102–114. Google Scholar
Y. He and J.F. Naughton , Anonymization of set-valued data via top-down, local generalization , Proc. VLDB ( 2009 ) . Google Scholar
J. Leskovec , D. Huttenlocher and J. Kleingerg , Signed networks in social media , Proc. CHI ( 2010 ) . Google Scholar
K. Liu and E. Terzi, Towards identity anonymization on graphs, Proc. SIGMOD Conference (2008) pp. 93–106. Google Scholar
L. Liu , J. Liu and J. Zhang , Privacy preservation of affinities in social networks , Proc. ICIS ( 2010 ) . Google Scholar
L. Liuet al., Privacy preservation in social networks with sensitive edge weights, Proc. SDM (2009) pp. 954–965. Google Scholar
G. Loukides and J. Shao, Expert Sysems with Application 38(4), 4559 (2011). Crossref, Web of Science, Google Scholar
A. Meyerson and R. Williams , On the complexity of optimal k-anonymity , Proc. PODS ( 2004 ) . Google Scholar
R. Motwani and S. U. Nabar, Anonymizing unstructured data, [cs.DB], 2008 , arXiv: 0810.5582v2 . Google Scholar
M. E. J. Newman , Phy. Rev. E 0605087 ( 2006 ) . Google Scholar
H. Park and K. Shim, Approximate algorithms for k-anonymity, Proc. of ACM SIGMOD International Conference on Management of Data (2007) pp. 67–78. Google Scholar
P. Samarati and L. Sweeny, Generalizing data to provide anonymity when disclosing information, Proc. of ACM Symposium on Principles of Database Systems (1998) p. 188. Google Scholar
L. Sweeny, Fuzziness and Knowledge-Based Systems 10(5), 557 (2002). Link, Web of Science, Google Scholar
S. L. Wang et al. , Anonymizing shortest paths on social network graphs , Proc. of Asian Conference on Intelligent Information and Database Systems ( 2011 ) . Google Scholar
B. Zhou and J. Pei, Preserving privacy in social networks against neighborhood attacks, Proc. ICDE (2008) pp. 506–515. Google Scholar
L. Zou , L. Chen and M. T. Ozsu , K-automorphism: A general framework for privacy preserving network publication , Proc. VLDB ( 2009 ) . Google Scholar