Abstract
The increasing popularity of social networks, such as online communities and telecommunication systems, has generated interesting knowledge discovery and data mining problems. Since social networks usually contain personal information of individuals, preserving privacy in the release of social network data becomes an important concern. An adversary can use many types of background knowledge to conduct an attack, such as topological structure and/or basic graph properties. Unfortunately, most of the previous studies on privacy preservation can deal with simple graphs only, and cannot be applied to weighted graphs. Since there exists numerous unique weight-based information in weighted graphs that can be used to attack a victim’s privacy, to resist such weight-based re-identification attacks becomes a great challenge. In this paper, we investigate the identity disclosure problem in weighted graphs. We propose k-possible anonymity to protect against weight-based attacks and develop a generalization based anonymization approach(named GA) to achieve k-possible anonymity for a weighted graph. Extensive experiments on real datasets show that the algorithm performs well in terms of protection it provides, and properties of the original weighed network can be recovered with relatively little bias through aggregation on a small number of sampled graphs.
The work is partially supported by the National Natural Science Foundation of China (Nos. 60973018, 60973020) and the Fundamental Research Funds for the Central Universities(Nos. N090504004, N100604013, N100704001, N090104001).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Li, Y., Shen, H.: Anonymizing graphs against weight-based attacks. In: International Conference on Data Mining Workshops(ICDMW 2010), pp. 491–498 (2010)
Backstrom, L., Dwork, C., Kleinberg, J.: Wherefore are thouR3579X?: Anonymized social networks, hiddern patterns and structural steganography. In: International World Wide Web Conference(WWW 2007), pp. 181–190 (2007)
Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD 2008), pp. 93–106. ACM Press, New York (2008)
Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In: Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE 2008), pp. 506–515 (2008)
Cheng, J., Fu, A.W.-C., Liu, J.: K-Isomorphism: Privacy preserving network publication against structural attacks. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD 2010), pp. 459–470 (2010)
Zou, L., Chen, L., Ozsu, M.T.: K-automorphism: A general framework for privacy preserving network publication. In: Proceedings of the 35th International Conference on Very Large Databases (VLDB 2009), vol. 2(1), pp. 946–957 (2009)
Wu, W., Xiao, Y., Wang, W., He, Z., Wang, Z.: K-Symmetry model for identity anonymization in social networks. In: Proceedings of the 13th International Conference on Extending Database Technology (EDBT 2010), pp. 111–122 (2010)
Ying, X., Wu, X.: Randomizing social networks: a spectrum preserving approach. In: Proceedings of the 2008 SIAM International Conference on Data Mining (SDM 2008), pp. 739–750 (2008)
Yuan, M., Chen, L., Yu, P.S.: Personalized privacy protection in social networks. Proceedings of the VLDB Endowment 4(2), 141–150 (2010)
Hay, M., Miklau, G., Jensen, D., Towsley, D.: Resisting structural re-identification in anonymized social networks. In: Proceedings of the 34th International Conference on Very Large Databases (VLDB 2008), pp. 102–114. ACM, New York (2008)
Campan, A., Truta, T.M.: A clustering approach for data and structural anonymity in social networks. In: Bonchi, F., Ferrari, E., Jiang, W., Malin, B. (eds.) PinKDD 2008. LNCS, vol. 5456, pp. 33–54. Springer, Heidelberg (2009)
Zheleva, E., Getoor, L.: Preserving the privacy of sensitive relationships in graph data. In: Bonchi, F., Malin, B., Saygın, Y. (eds.) PinKDD 2007. LNCS, vol. 4890, pp. 153–171. Springer, Heidelberg (2008)
Das, S., Egecioglu, O., Abbadi, A.E.: Anonymizing weighted social network graphs. In: The 26th International Conference on Data Engineering, ICDE 2010 (2010)
Liu, L., Wang, J., Liu, J., Zhang, J.: Privacy preservation in social networks with sensitive edge weights. In: 2009 SIAM International Conference on Data Mining(SDM 2009), Sparks, Nevada, pp. 954–965 (April 2009)
Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 0605087 (2006)
Newman, M.E.J.: The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA 98, 404–409 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, X., Yang, X. (2011). A Generalization Based Approach for Anonymizing Weighted Social Network Graphs. In: Wang, H., Li, S., Oyama, S., Hu, X., Qian, T. (eds) Web-Age Information Management. WAIM 2011. Lecture Notes in Computer Science, vol 6897. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23535-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-23535-1_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23534-4
Online ISBN: 978-3-642-23535-1
eBook Packages: Computer ScienceComputer Science (R0)