Cited By
View all- Tsai YWang SHong TKao H(2015)Extending [K 1 , K 2 ] Anonymization of Shortest Paths for Social NetworksMultidisciplinary Social Networks Research10.1007/978-3-662-48319-0_15(187-199)Online publication date: 25-Aug-2015
[K1, K2]-anonymization of Shortest Paths
Pages 317 - 321
Abstract
Privacy preserving network publishing has been studied extensively in recent years. Although more works have adopted un-weighted graphs to model network relationships, weighted graph modeling can provide deeper analysis of the degree of relationships. Previous works on weighted graph privacy have concentrated on preserving the shortest path characteristic between pairs of vertices. Two common types of privacy have been proposed. One type of privacy tried to add random noise edge weights to the graph but still maintain the same shortest path. The other privacy, k-shortest path privacy, minimally perturbed edge weights so that there exists k shortest paths. However, the k-shortest path privacy only considers anonymizing same fixed number of shortest paths for all pairs of source and destination vertices. In this work, we present a new concept called [k1, k2]-shortest path privacy to allow different number of shortest paths for different pairs of vertices. A published network graph with [k1, k2]-shortest path privacy has at least k' indistinguishable shortest paths between the source and destination vertices, where k1 ≦ k' ≦ k2. A heuristic algorithm based on modifying only Non-Visited (NV) edges is proposed and experimental results showing the feasibility and characteristics of the proposed approach are presented.
References
[1]
L. Backstrom, D. P. Huttenlocher, J. M. Kleinberg, and X. Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In Proc. KDD, pp. 44--54.
[2]
L. Backstrom, C. Dwork, and J. M. Kleinberg. 2007. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In Proc. of WWW, pp. 181--190.
[3]
S. Bhagat, G. Cormode, B. Krishnamurthy, and D. Srivastava. 2009. Class-based Graph Anonymization for Social Network Data, In Proc. VLDB, pp. 766--777.
[4]
J. Cheng, A. Fu, and J. Liu. 2010. K-isomorphism: privacy preserving network publication against structural attacks. In Proc. SIGMOD conference, pp. 459--470.
[5]
S. Das, O. Egecioglu, and A.E. Abbadi. 2010. Anonymizing weighted social network graphs. In Proc. ICDE, pp. 904--907.
[6]
Jun Gao, Jeffery Yu Xu, Ruoming Jin. 2011. Jiashuai Zhou, Tengjiao Wang and Dongqing Yang. Neighborhood-Privacy Protected Shortest Distance Computing in Cloud. In Proc. SIGMOD.
[7]
M. Hay, G. Miklau, D. Jensen, D. F. Towsley, and P. Weis. Resisting structural re-identification in anonymized social networks. In Proc. PVLDB, 1(1):102--114, 2008.
[8]
H. Hinds and R.M. Lee. 2008. Social Network Stucture as Critical Success Condition for Virtual Communities, In Proc. HICSS.
[9]
J. Leskovec, D. Huttenlocher, and J. Kleingerg. 2010. Signed networks in social media. In Proc. CHI.
[10]
K. Liu and E. Terzi. 2008. Towards identity anonymization on graphs. In Proc. SIGMOD Conference, pp. 93--106.
[11]
L. Liu, J. Liu, and J. Zhang. Privacy preservation of affinities in social networks. In Proc. ICIS, 2010.
[12]
L. Liu, J. Wang, J. Liu, and J. Zhang. 2009. Privacy preservation in social networks with sensitive edge weights. In Proc. SDM, pp. 954--965.
[13]
X. Liu and X. Yang. 2011. A Generalization Based Approach for Anonymizing Weighted Social Network Graphs, In Proc. WAIM, pp. 118--130.
[14]
M. Madden, A Pew Internet Report. 2012. http://www.isaca.org/Groups/Professional-English/privacy-data-protection/GroupDocuments/PIP_Privacy mgt on social media sites Feb 2012.pdf
[15]
A. Narayanan and V. Shmatikov. 2009. De-anonymizing Social Networks, In Proc. IEEE Security and Privacy, pp. 173--187.
[16]
M. E. J. Newman. 2001. The Structure of Scientific Collaboration Networks, In Proc. Natl. Acad. Sci. USA 98, pp. 404--409.
[17]
S.L. Wang, Z.Z. Tsai, T.P. Hong, and I-Hsien Ting. 2011. Anonymizing shortest paths on social network graphs. In Proc. of Asian Conference on Intelligent Information and Database Systems.
[18]
M. Yuan, L. Chen. 2011. Node Protection in Weighted Social Networks, DASFAA, pp. 123--137.
[19]
M. Yuan, L. Chen, P.S. Yu. 2010. Personalized Privacy Protection in Social Networks, In Proc. VLDB.
[20]
B. Zhou and J. Pei. 2008. Preserving privacy in social networks against neighborhood attacks. In Proc. ICDE, pp. 506--515.
[21]
L. Zou, L. Chen, and M. T. Ozsu. 2009. K-automorphism: A general framework for privacy preserving network publication. In Proc. VLDB.
Index Terms
- [K1, K2]-anonymization of Shortest Paths
Recommendations
Anonymizing shortest paths on social network graphs
ACIIDS'11: Proceedings of the Third international conference on Intelligent information and database systems - Volume Part ISocial networking is gaining enormous popularity in the past few years. However, the popularity may also bring unexpected consequences for users regarding safety and privacy concerns. To prevent privacy being breached and modeling a social network as a ...
Anonymizing Multiple K-anonymous Shortest Paths for Social Graphs
IBICA '11: Proceedings of the 2011 Second International Conference on Innovations in Bio-inspired Computing and ApplicationsTo preserve privacy, k-anonymity on relational, set-valued, and graph data have been studied extensively in recent years. Information on social networks can be modeled as un-weighted or weighted graph data for sharing and publishing. We have previously ...
K-anonymous path privacy on social graphs
Growing popularity of social networking not only brings the convenience of information sharing but also concerns of privacy breaches. Information on social networks can be modeled as un-weighted or weighted graph data. To preserve privacy, k-anonymity ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2014
464 pages
ISBN:9781450330084
DOI:10.1145/2684103
- General Chair:
- Shyue-Liang Leon Wang,
- Program Chairs:
- Yu-Hui Tao,
- Liming Chen,
- Chung-Nan Lee
Copyright © 2014 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
- JKU: Johannes Kepler Universität Linz
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 December 2014
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
MoMM '14
MoMM '14: The 12th International Conference on Advances in Mobile Computing and Multimedia
December 8 - 10, 2014
Kaohsiung, Taiwan
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 58Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Sep 2024
Other Metrics
Citations
Cited By
View all- Tsai YWang SHong TKao H(2015)Extending [K 1 , K 2 ] Anonymization of Shortest Paths for Social NetworksMultidisciplinary Social Networks Research10.1007/978-3-662-48319-0_15(187-199)Online publication date: 25-Aug-2015
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in