Personalized Privacy Preserving Method for Social Networks Graph k-Anonymization

Document Type : Computer and Network Security-Ghaemi

Authors

• Hourie Mehrabiun ¹
• Behnaz Omoomi ²

¹ Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran.

² Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran

10.22067/cke.2023.63240.0

Abstract

Nowadays, with the development of social networks, the risk of disclosure of users’ information has also increased, which has caused serious concerns among users. Accordingly, privacy preserving on social networks is a significant issue that has attracted much attention. Although there are various methods for preserving privacy on social networks, most of the existing methods are based on the universal approach that considers the same level of preservation for all users and only some of them consider individual personalized privacy requirements, which is very limited, and those are based on users’ willing to share friends list and sensitive information with other users.  This study focuses on a new scheme of personalized privacy preserving based on k-anonymity which can anonymize the social network graph based on the personalized privacy requirements of each individual. We develop a Modified Degree Privacy Level Sequence (MDPLS) Algorithm and execute experiments on two datasets. The results of the experiments show that in this new method of social network graph anonymization, when we consider the personalized privacy requirements, the costs of the anonymity process are reduced and data utility is improved in comparison with the situation where we only consider one level of privacy for all users, i.e., universal approach.

Keywords

• Anonymous Social Network Graph
• Personalized Privacy
• Privacy Preserving
• Social Network

Main Subjects

• Computer and Network Security

---

References

[1] A. Singh, D. Bansal, S. Sofat, “Privacy preserving techniques in social networks data publishing-a review”, International Journal of Computer Applications, vol. 87, no. 15,2014

[2] E. Zheleva, L. Getoor, “Preserving the privacy of sensitive relationships in graph data,” in: International Workshop on Privacy, Security, and Trust in KDD, pp. 153-171: Springer, 2007.

[3] K. Liu, E. Terzi, “Towards identity anonymization on graphs,” in: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 93-106: ACM, 2008.

[4] J. Jiao, P. Liu, X. Li, “A personalized privacy preserving method for publishing social network data,” in: International Conference on Theory and Applications of Models of Computation, pp. 141-157: Springer, 2014.

[5] L. Lan, H. Jin, Y. Lu, “Personalized anonymity in social networks data publication,” in: 2011 IEEE International

Conference on Computer Science and Automation Engineering,

vol. 1, pp. 479-482: IEEE, 2011.

[6] M. Yuan, L. Chen, P. S. Yu, “Personalized privacy protection in social networks,” Proceedings of the VLDB Endowment, vol. 4 no. 2, pp. 141-150, 2010.

[7] P. Samarati, L. Sweeney, “Generalizing data to provide anonymity when disclosing information,” in: PODS, vol. 98, no. 10.1145 pp. 275487-275508, 1998

[8] T. M. Truta, B. Vinay, “Privacy protection: p-sensitive k-anonymity property,” in: 22nd International Conference on Data Engineering Workshops (ICDEW’06), pp. 94-94: IEEE, 2006.

[9] P. Samarati, “Protecting respondents identities in microdata release,” IEEE transactions on Knowledge and Data Engineering, vol. 13, no. 6 pp. 1010-1027, 2001.

[10] L. Sweeney, “Achieving k-anonymity privacy protection using generalization and suppression,” International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 571-588, 2002.

[11] C. C. Aggarwal, P. S. Yu, “On variable constraints in privacy preserving data mining,” in: Proceedings of the 2005 SIAM International Conference on Data Mining, SIAM, pp. 115-125, 2005.

[12] C. C. Aggarwal, S. Y. Philip, “A condensation approach to privacy preserving data mining,” in: International Conference on Extending Database Technology, Springer, pp. 183-199, 2004.

[13] X. Xiao, Y. Tao, “Personalized privacy preservation,” in: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, ACM, pp. 229-240, 2006.

[14] Y. Shen, H. Shao, Y. Li, “Research on the personalized privacy preserving distributed data mining,” in: 2009 Second International Conference on Future Information Technology and Management Engineering, IEEE, pp. 436-439, 2009

[15] Y. Xu, X. Qin, Z. Yang, Y. Yang, K. Li, “A personalized k-anonymity privacy preserving method,” Journal of Information & Computational Science, vol. 10, no. 1, 2013 pp.  139-155.

[16] R. Ford, T. M. Truta, A. Campan, “P-sensitive k-anonymity for social networks,” DMIN, vol.  9, pp. 403-409, 2009

[17] A. Campan, T. M. Truta, “A clustering approach for data and structural anonymity in social networks,” in: International Workshop on Privacy, Security, and Trust in KDD, 2008.

[18] A. Campan, T. M. Truta, j. Miller, R. Sinca, “A clustering approach for achieving data privacy,” in: International Conference on Data Mining DMIN, 2007.

[19] A. Machanavajjhala, J. Gehrke, D. Kifer, M. Venkitasubramaniam, “ldiversity: Privacy beyond k-anonymity,” in: 22nd International Conference on Data Engineering (ICDE’06), IEEE, pp. 24-24, 2006.

[20] N. Li, T. Li, S. Venkatasubramanian, “t-closeness: Privacy beyond k-anonymity and l-diversity,” in: 2007 IEEE 23rd International Conference on Data Engineering, IEEE, pp. 106-115, 2007.

[21] G. Aggarwal, R. Panigrahy, T. Feder, D. Thomas, K. Kenthapadi,S. Khuller, A. Zhu, “Achieving anonymity via clustering,” ACM Transactions on Algorithms (TALG), vol. 6, no. 3, pp. 1-19, 2010.

[22] T. Li, N. Li, J. Zhang, I. Molloy, Slicing: “A new approach for privacy preserving data publishing,” IEEE Transactions on Knowledge and Data Engineering, vol. 24, no. 3, pp.  561-574, 2010.

[23] X. Xiao, Y. Tao, “Anatomy: Simple and effective privacy preservation,” in: Proceedings of the 32nd International Conference on Very Large Data  Bases, VLDB Endowment, pp. 139-150, 2006.

[24] F. Amiri, N. Yazdani, A. Shakery, A. H. Chinaei, “Hierarchical anonymization algorithms against background knowledge attack in data releasing,” Knowledge-Based Systems, vol. 101, pp. 71-89, 2016.

[25] M. Hay, G. Miklau, D. Jensen, P. Weis, S. Srivastava, “Anonymizing social networks,” Computer science department faculty publication series, pp.1-180, 2007.

[26] B. Zhou, J. Pei, “Preserving privacy in social networks against neighborhood attacks,” in: 2008 IEEE 24th International Conference on Data Engineering, pp. 506-515, 2008.

 [27] A. Campan, T. M. Truta, “Data and structural k-anonymity in social networks”, in: International Workshop on Privacy, Security, and Trust in KDD, Springer, pp. 33-54, 2009.

[28] L. Zou, L. Chen, M. T. Ozsu, “K-automorphism: A general framework for ¨privacy preserving network publication,” Proceedings of the VLDB Endowment, vol. 2, no. 1, pp.  946-957, 2009.

[29] B. Zhou, J. Pei, “The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks,” Knowledge and Information Systems, vol. 28, no. 1, pp.  47-77, 2009.

[30] M. Yuan, L. Chen, S. Y. Philip, T. Yu, “Protecting sensitive labels in social network data anonymization,” IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 3, pp. 633-647, 2011.

[31] M. I. H. Ninggal, J. H. Abawajy, “Utility-aware social network graph anonymization,” Journal of Network and Computer Applications, vol. 56, pp. 137-148, 2015.

[32] K. R. Macwan, S. J. Patel, “k-degree anonymity model for social network data publishing,” Advances in Electrical and Computer Engineering, vol. 17, no. 4, pp. 117-125, 2017

[33] K. S. Babu, S. K. Jena, J. Hota, B. Moharana, “Anonymizing social networks: A generalization approach,” Computers & Electrical Engineering, vol. 39, no. 7, pp.  1947-1961, 2013.