MLDA: a multi-level k-degree anonymity scheme on directed social network graphs

Abstract

With the emergence of network-centric data, social network graph publishing is conducive to data analysts to mine the value of social networks, analyze the social behavior of individuals or groups, implement personalized recommendations, and so on. However, published social network graphs are often subject to re-identification attacks from adversaries, which results in the leakage of users’ privacy. The k-anonymity technology is widely used in the field of graph publishing, which is quite effective to resist re-identification attacks. However, the current researches still exist some issues to be solved: the protection of directed graphs is less concerned than that of undirected graphs; the protection of graph structure is often ignored while achieving the protection of nodes’ identities; the same protection is performed for different users, which doesn’t meet the different privacy requirements of users. Therefore, to address the above issues, a multi-level k-degree anonymity (MLDA) scheme on directed social network graphs is proposed in this paper. First, node sets with different importance are divided by the firefly algorithm and constrained connectedness upper approximation, and they are performed different k-degree anonymity protection to meet the different privacy requirements of users. Second, a new graph anonymity method is proposed, which achieves the addition and removal of edges with the help of fake nodes. In addition, to improve the utility of the anonymized graph, a new edge cost criterion is proposed, which is used to select the most appropriate edge to be removed. Third, to protect the community structure of the original graph as much as possible, fake nodes contained in a same community are merged prior to fake nodes contained in different communities. Experimental results on real datasets show that the newly proposed MLDA scheme is effective to balance the privacy and utility of the anonymized graph.

Graphical abstract

Keywords

directed social network graph / graph publishing / k-degree anonymity / community structure / graph utility

Yuanjing Hao received the BS degree in computer science and technology from Henan Normal University, China in 2019. She is currently a PhD candidate of Guilin University of Electronic Technology, China. Her research interests include information security and social network graph data privacy

Long Li received the PhD degree from Guilin University of Electronic Technology, China in 2018. He is now a lecturer with the School of Computer Science and Information Security, Guilin University of Electronic Technology, China and undertakes postdoctoral research in Jinan University, China. His research interests include cryptographic protocols, privacy-preserving technologies, and AI ethics

Liang Chang received the PhD degree in computer science from the Institute of Computing Technology, Chinese Academy of Sciences, China. He is currently a Professor with the School of Computer Science and Information Security, Guilin University of Electronic Technology, China. His research interests include information security, knowledge representation and reasoning, description logics, and the semantic Web

Tianlong Gu received the PhD degree from Zhejiang University, China in 1996. From 1998 to 2002, he was a Post-Doctoral Fellow with the School of Electrical and Computer Engineering, Curtin University, Australia and a Research Fellow with the School of Engineering, Murdoch University, Australia. He is currently a Professor and the director of the Engineering Research Center of Trustworthy AI (Ministry of Education), Jinan University, China. His research interests include formal methods, trustworthy artificial intelligence, artificial intelligence ethics, and data governance

References

[1] Ferri F, Grifoni P, Guzzo T . New forms of social and professional digital relationships: the case of facebook. Social Network Analysis and Mining, 2012, 2( 2): 121–137

[2] Yang D, Qu B, Cudré-Mauroux P . Privacy-preserving social media data publishing for personalized ranking-based recommendation. IEEE Transactions on Knowledge and Data Engineering, 2019, 31( 3): 507–520

[3] Langari R K, Sardar S, Mousavi S A A, Radfar R . Combined fuzzy clustering and firefly algorithm for privacy preserving in social networks. Expert Systems with Applications, 2020, 141: 112968

[4] Wang X, Li Y . Geo-social network publication based on differential privacy. Frontiers of Computer Science, 2018, 12( 6): 1264–1266

[5] Huang H, Zhang D, Xiao F, Wang K, Gu J, Wang R . Privacy-preserving approach PBCN in social network with differential privacy. IEEE Transactions on Network and Service Management, 2020, 17( 2): 931–945

[6] Jian X, Wang Y, Chen L . Publishing graphs under node differential privacy. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 4): 4164–4177

[7] Pei X, Deng X, Tian S, Xue K. Efficient privacy preserving graph neural network for node classification. In: Proceedings of ICASSP 2023−2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2023, 1−5

[8] Zhang S, Ni W, Fu N. Community preserved social graph publishing with node differential privacy. In: Proceedings of 2020 IEEE International Conference on Data Mining (ICDM). 2020, 1400−1405

[9] Casas-Roma J, Herrera-Joancomartí J, Torra V . A survey of graph-modification techniques for privacy-preserving on networks. Artificial Intelligence Review, 2017, 47( 3): 341–366

[10] Liu K, Terzi E. Towards identity anonymization on graphs. In: Proceedings of 2008 ACM SIGMOD International Conference on Management of Data. 2008, 93−106

[11] Xiang S, Cheng D, Zhang J, Ma Z, Wang X, Zhang Y. Efficient learning-based community-preserving graph generation. In: Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE). 2022, 1982−1994

[12] Ji T, Luo C, Guo Y, Wang Q, Yu L, Li P . Community detection in online social networks: a differentially private and parsimonious approach. IEEE Transactions on Computational Social Systems, 2020, 7( 1): 151–163

[13] Rousseau F, Casas-Roma J, Vazirgiannis M . Community-preserving anonymization of graphs. Knowledge and Information Systems, 2018, 54( 2): 315–343

[14] Sweeney L . k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 2002, 10( 5): 557–570

[15] Kiabod M, Dehkordi M N, Barekatain B . TSRAM: A time-saving k-degree anonymization method in social network. Expert Systems with Applications, 2019, 125: 378–396

[16] Kiabod M, Dehkordi M N, Barekatain B . A fast graph modification method for social network anonymization. Expert Systems with Applications, 2021, 180: 115148

[17] Wang H, Wang W, Zhou X, Sun H, Zhao J, Yu X, Cui Z. Firefly algorithm with neighborhood attraction. Information Sciences, 2017, 382−383: 374−387

[18] Casas-Roma J, Herrera-Joancomartí J, Torra V . k-degree anonymity and edge selection: improving data utility in large networks. Knowledge and Information Systems, 2017, 50( 2): 447–474

[19] Xiang N, Ma X. TKDA: An improved method for k-degree anonymity in social graphs. In: Proceedings of 2022 IEEE Symposium on Computers and Communications (ISCC). 2022, 1−6

[20] Ding X, Wang C, Choo K K R, Jin H . A novel privacy preserving framework for large scale graph data publishing. IEEE Transactions on Knowledge and Data Engineering, 2019, 33( 2): 331–343

[21] Lin S H, Xiao R . Towards publishing directed social network data with k-degree anonymization. Concurrency and Computation: Practice and Experience, 2022, 34( 24): e7226

[22] Casas-Roma J, Salas J, Malliaros F D, Vazirgiannis M . k-degree anonymity on directed networks. Knowledge and Information Systems, 2019, 61( 3): 1743–1768

[23] Hoang A T, Carminati B, Ferrari E. Cluster-based anonymization of knowledge graphs. In: Proceedings of the 18th International Conference on Applied Cryptography and Network Security. 2020, 104−123

[24] Hoang A T, Carminati B, Ferrari E. Privacy-preserving sequential publishing of knowledge graphs. In: Proceedings of the 37th IEEE International Conference on Data Engineering (ICDE). 2021, 2021−2026

[25] Hoang A T, Carminati B, Ferrari E. Time-aware anonymization of knowledge graphs. ACM Transactions on Privacy and Security, 2022, doi: 10.1145/3563694

[26] Ren W L, Ghazinour K, Lian X . kt-safety: Graph release via k-anonymity and t-closeness. IEEE Transactions on Knowledge and Data Engineering, 2022, 35( 9): 9102–9113

[27] Zhang H, Lin L, Xu L, Wang X . Graph partition based privacy-preserving scheme in social networks. Journal of Network and Computer Applications, 2021, 195: 103214

[28] Mortazavi R, Erfani S H . Gram: An efficient (k, l) graph anonymization method. Expert Systems with Applications, 2020, 153: 113454

[29] Assam R, Hassani M, Brysch M, Seidl T. (k, d)-core anonymity: structural anonymization of massive networks. In: Proceedings of the 26th International Conference on Scientific and Statistical Database Management. 2014, 17

[30] Tai C H, Yu P S, Yang D N, Chen M S. Privacy-preserving social network publication against friendship attacks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 1262−1270

[31] Jain D K, Ren X, Jiang D . A personalized α, β, l, k-anonymity model of social network for protecting privacy. Wireless Communications & Mobile Computing, 2022, 2022: 7187528

[32] Ma T, Liu Q, Cao J, Tian Y, Al-Dhelaan A, Al-Rodhaan M . Lgiem: Global and local node influence based community detection. Future Generation Computer Systems, 2020, 105: 533–546

[33] Kumar S, Kumar P . Upper approximation based privacy preserving in online social networks. Expert Systems with Applications, 2017, 88: 276–289

[34] Zhang X, Li J, Liu J, Zhang H, Liu L . Social network sensitive area perturbance method based on firefly algorithm. IEEE Access, 2019, 7: 137759–137769

[35] Jain L, Katarya R . Discover opinion leader in online social network using firefly algorithm. Expert Systems with Applications, 2019, 122: 1–15

[36] Zhang X, Liu J, Li J, Liu L . Large-scale dynamic social network directed graph K-In&Out-degree anonymity algorithm for protecting community structure. IEEE Access, 2019, 7( 1): 108371–108383

[37] Yin H, Benson A R, Leskovec J, Gleich D F. Local higher-order graph clustering. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 555−564

[38] Adamic L A, Glance N. The political blogosphere and the 2004 U.S. election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery. 2005, 36−43

[39] Rossi R A, Ahmed N K. The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 4292−4293

[40] Danon L, Díaz-Guilera A, Duch J, Arenas A . Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005( 9): P09008

[41] Hubert L, Arabie P . Comparing partitions. Journal of Classification, 1985, 2( 1): 193–218

[42] Dongen S. Performance criteria for graph clustering and markov cluster experiments. Amsterdam: CWI (Centre for Mathematics and Computer Science), 2000

[43] Rand W M . Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 1971, 66( 336): 846–850

[44] Wagner I, Eckhoff D . Technical privacy metrics: a systematic survey. ACM Computing Surveys, 2019, 51( 3): 57

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 61966009, U22A2099).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2024 Higher Education Press