Abstract
Privacy is a great concern when information are published and shared. Privacy-preserving social network data publishing has been studied extensively in recent years. Early works had concentrated on protecting sensitive nodes and links information to prevent privacy breaches. Recent studies start to focus on preserving sensitive edge weight information such as shortest paths. Two types of privacy on sensitive shortest paths 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 at least k shortest paths. However, there might be insufficient paths that can be modified to the same path length. In this work, we extend previously proposed [k 1 , k 2 ]-shortest path privacy, k 1 ≦k≦k 2 , to not only anonymizing different number of shortest paths for different source and destination vertex pair, but also modifying different types of edges, such as partially visited edges. Numerical experiments showing the characteristics of the proposed algorithm is given. The proposed algorithm is more efficient in running time than the previous work with similar perturbed ratios of edges.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Backstrom, L., Huttenlocher, D.P., Kleinberg, J.M., Lan, X.: Group formation in large social networks: membership, growth, and evolution. In: Proceedings of KDD, pp. 44–54 (2006)
Backstrom, L., Dwork, C., Kleinberg, J.M.: Wherefore art thou r3579x?: anonymized social networks, hidden patterns. and structural steganography. In: Proceedings of World Wide Web, pp. 181–190 (2007)
Bhagat, S., Cormode, G., Krishnamurthy, B., Srivastava, D.: Class-based graph anonymization for social network data. In: Proceedings of Very Large Data Bases, pp. 766–777 (2009)
Banisar, D.: Freedom of information around the world 2006 – A global survey of access to government information Laws. www.privacyinternational.org/foi/survey
Cheng, J., Fu, A., Liu, J.: K-isomorphism: privacy preserving network publication against structural attacks. In: Proceedings of ACM SIGMOD Conference, pp. 459–470 (2010)
Das, S., Egecioglu, O., Abbad, A.E.: Anonymizing weighted social network graphs. In: Proceedings of International Conference on Data Engineering, pp. 904–907 (2010)
Gao, J., Xu, Y., Jin, R.M., Zhou, J.S., Wang, T.J., Yang, D.Q.: Neighborhood-privacy protected shortest distance computing in cloud. In: Proceedings of ACM SIGMOD Conference, pp. 409–420 (2011)
Hay, M., Miklau, G., Jensen, D., Towsley, D.F., Weis, P.: Resisting structural re-identification in anonymized social networks. Proceedings of the VLDB Endowment 1(1), 102–114 (2008)
Inkpen, A.: The Japanese corporate network transferred to North America: implications of North American firms. The International Executive 36(4), 411–433 (1994)
Leskovec, J., Huttenlocher, D., Kleingerg, J.: Signed networks in social media. In: Proceedings of CHI Conference on Human Factors in Computing Systems, pp. 1361–1370 (2010)
Li, Y., Shenm, H.: On Identity Disclosure in Weighted Graphs. In: Proceedings of the 11th International Conference on Parallel and Distributed Computing, Applications and Technologies, pp.166–174 (2010)
Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of ACM SIGMOD Conference, pp. 93–106 (2008)
Liu, L., Liu, J., Zhang, J.: Privacy preservation of affinities in social networks. In: Proceedings of International Conference on Information Systems (2010)
Liu, L., Wang, J., Liu, J., Zhang, J.: Privacy preservation in social networks with sensitive edge weights. In: Proceedings of the SIAM International Conference on Data Mining, pp. 954–965 (2009)
Liu, X., Yang, X.: A Generalization Based Approach for Anonymizing Weighted Social Network Graphs. In: Wang, H., Li, S., Oyama, S., Hu, X., Qian, T. (eds.) WAIM 2011. LNCS, vol. 6897, pp. 118–130. Springer, Heidelberg (2011)
Newman, M.E.J.: The structure of scientific collaboration networks. In: Proceedings of Natl. Acad. Sci. 98, pp. 404409 (2001)
Nobari, S., Karras, P., Pang, H., Bressan, S.: L-opacity: linkage-aware graph anonymization. In: Proceedings of 17th International Conference on Extending Database Technology, pp. 583–594 (2014)
Wang, S.-L., Tsai, Z.-Z., Hong, T.-P., Ting, I.-H.: Anonymizing Shortest Paths on Social Network Graphs. In: Nguyen, N.T., Kim, C.-G., Janiak, A. (eds.) ACIIDS 2011, Part I. LNCS, vol. 6591, pp. 129–136. Springer, Heidelberg (2011)
Tsai, Y.C., Wang, S.L., Kao, H.Y., Hong, T.P.: Edge types vs privacy in K-anonymization of shortest paths. In Applied Soft Computing 31, 348–359 (2015)
Tsai, Y.C., Wang, S.L., Kao, H.Y., Hong, T.P.: [k1, k2]-anonymization of Shortest Paths, In: Proceedings of 4th International Workshop on Intelligent Data Analysis and Management (2014)
Yuan, M., Chen, L., Yu, P.S.: Personalized privacy protection in social networks. In: Proceedings of the 36rd International Conference on Very Large Data Bases, pp.141–150 (2010)
Yuan, M., Chen, L.: Node Protection in Weighted Social Networks. In: Yu, J.X., Kim, M.H., Unland, R. (eds.) DASFAA 2011, Part I. LNCS, vol. 6587, pp. 123–137. Springer, Heidelberg (2011)
Yen, J.Y.: A shortest path algorithm, Ph.D. dissertation, University of California, Berkeley (1970)
Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In: Proceedings of the 24th International Conference on Data Engineering, pp. 506–515 (2008)
Zou, L., Chen, L., Ozsu, M.T.: K-automorphism: A general framework for privacy preserving network publication. In: Proceedings of the 35rd International Conference on Very Large Data Bases, pp. 946–957 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tsai, YC., Wang, SL., Hong, TP., Kao, HY. (2015). Extending [K 1 , K 2 ] Anonymization of Shortest Paths for Social Networks. In: Wang, L., Uesugi, S., Ting, IH., Okuhara, K., Wang, K. (eds) Multidisciplinary Social Networks Research. MISNC 2015. Communications in Computer and Information Science, vol 540. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48319-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-662-48319-0_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48318-3
Online ISBN: 978-3-662-48319-0
eBook Packages: Computer ScienceComputer Science (R0)