A graph generating method based on local differential privacy for preserving link relationships of social networks

Laifeng Lu

¹School of Mathematics and Computer Applications, Shangluo College, Shangluo, Shaanxi, 72600, China

²School of Mathematics and Statistics, Shaanxi Normal University, Xiˆaan, Shaanxi, 710119, China

³School of Economics and Management, Shangluo College, Shangluo, Shaanxi, 72600, China

⁴School of Computer Science, Shaanxi Normal University, Xiˆaan, Shaanxi, 710119, China

*Corresponding author

With the widespread popularity of social networks, there are serious privacy issues related to the graph data of social networks. To address these issues, many differential privacy based graph generating methods have been proposed. However, these methods mainly focus on preserving the properties of the graph and ignore the preservation of node link relationships. To further preserve the link relationship of each user in the distributed environment of Social Networks while providing effective data utility, a local differential privacy graph generating method is proposed, in which the randomized response is utilized to modify the link relationships of nodes and all modified subgraphs of each node are merged to get a synthetic graph to preserve the link privacy of each node. In addition, the 2-hop subgraph based node encoding of each node is adopted to reduce the disturbance caused by the local differential privacy. The unbiased estimate of random response and the node similarity are applied to maintain data utility. Theoretical analysis demonstrates that the designed method satisfies differential privacy while maintaining data utility. The experimental results indicate the effectiveness of this method.

Local differential privacy, link relationship, node coding, randomized response, unbiased estimate

Jun Yan, Yijun Zhang, Laifeng Lu, Yi Tian, and Yihui Zhou (2024). A graph generating method based on local differential privacy for preserving link relationships of social networks. Journal of Networking and Network Applications, Volume 4, Issue 4, pp. 145–156. https://doi.org/10.33969/J-NaNA.2024.040401.

[1] M. Umar, J. Wang, L. Liu, Z. Guo and S. Wang, “Physical layer authentication in the internet of vehicles based on signal propagation attribute prediction, ”Journal of Networking and Network Applications, vol.3, no.1, pp.1-10, 2023

[2] A. Rejeb, K. Rejeb, H. Treiblmaier, A. Appolloni, S. Alghamdi, Y. Alhasawi and M. Iranmanesh, “The Internet of Things (IoT) in healthcare: Taking stock and moving forward, ”Internet of Things, vol.22, pp.1-29, 2023.

[3] Z. Guo, J. He, Y. Zhang, S. Zhao, Y. Shen and X. Jiang, “Covert Communications in Satellite Internet: A Survey, ”Journal of Networking and Network Applications, vol.2, no.3, pp.120-128, 2022.

[4] T. Hennig-Thurau, D. N. Aliman, A. M. Herting, G. P. Cziehso, M. Linder and R. V. K¨¹bler, “Social interactions in the metaverse: Framework, initial evidence, and research roadmap, ”J ACAD MARKET SCI, vol.51, no.4, pp.889-913, 2023.

[5] C. Wu, “Data privacy : From transparency to fairness,” TECHNOL SOC, vol.76, pp.1-10, 2024.

[6] M. Bhattacharya, S. Roy, S. Chattopadhyay, A. K. Das and S. Shetty, “A comprehensive survey on online social networks security and privacy issues: Threats, machine learning-based solutions, and open challenges. Security and Privacy, ” SECUR PRIVACY, vol.6, no.1, pp.1-28, 2023.

[7] G. J. X. Dance, M. LaForgia and N. Confessore, “As Facebook raised a privacy wall, it carved an opening for tech giants, ”The New York Times, vol.18, pp.1-9, 2018.

[8] A. Zulkifli, “TikTok in 2022 : revisiting data and privacy,” Computer, vol.55, no.6, pp.77-80, 2022.

[9] H. Wang, Z. Cui, R. Liu, L. Fang and Y. Sha, “A multi-type transferable method for missing link prediction in heterogeneous social networks, ”IEEE T KNOWL DATA EN, vol.35, no.11, pp.10981-10991, 2023.

[10] A. Narayanan and V. Shmatikov, “De-anonymizing social networks,”in Proceedings of the 30th IEEE symposium on security and privacy, 2009, pp.173-187.

[11] S. A. Myers, A. Sharma, P. Gupta and J. Lin, “Information network or social network? The structure of the Twitter follow graph,”in Proceedings of the 23rd International Conference on World Wide Web,2014,pp.493-498.

[12] H. Jiang, J. Pei, D. Yu, J. Yu, B. Gong and X. Cheng, “Applications of differential privacy in social network analysis : A survey,” IEEE T KNOWL DATA EN, vol.35, no.1, pp.108-127, 2023.

[13] Y. Li, M. Purcell, T. Rakotoarivelo, D. Smith, T. Ranbaduge and K. S. Ng, “Private graph data release: A survey,” ACM COMPUT SURV, vol.55, no.11, pp.1-39, 2023.

[14] S. Zhang, W. W. Ni and N. Fu, “Differentially private graph publishing with degree distribution preservation, ”COMPUT SECUR, vol.106, pp.1-17, 2021.

[15] J. Abawajy, M. I. H. Ninggal and T. Herawan, “Vertex re-identification at-tack using neighbourhood-pair properties, ”CONCURR COMP-PRACT E, vol.28, no.10, pp.2906-2919, 2016.

[16] Q. Ye, H. Hu, M. H. Au, X. Meng and X. Xiao, “LF-GDPR:A framework for estimating graph metrics with local differential privacy, ”IEEE T KNOWL DATA EN, vol.34, no.10, pp.4905-4920, 2022.

[17] P. Liu, Y. X. Xu, Q. Jiang, Y. Tang, Y. Guo, L. E. Wang and X. Li, “Local differential privacy for social network publishing, ” Neurocomputing, vol.391, pp.273-279, 2020.

[18] Z. Qin, T. Yu, Y. Yang, I. Khalil, X. Xiao and K. Ren, “Generating synthetic decentralized social graphs with local differential privacy,” in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2017, pp.425-438.

[19] C. Wei, S. Ji, C. Liu, W. Chen and T. Wang, “Asgldp:Collecting and gener-ating decentralized attributed graphs with local differential privacy, ”IEEE T INF FOREN SEC, vol.15, pp.3239-3254, 2020.

[20] L. Hou, W. Ni, S. Zhang, N. Fu and D. Zhang, “PPDU:dynamic graph publication with local differential privacy,” KNOWL INF SYST, vol.65, no.7, pp.2965-2989, 2023.

[21] X. Ying and X. Wu, “Randomizing social networks: a spectrum preserv-ing approach,” in Proceedings of SIAM International Conference on Data Mining, 2008, pp.739-750.

[22] K. Hayawi, P. H. Ho, S .S .Mathew and L. Peng, “k-Anonymous Query Scheme on the Internet of Things: a Zero Trust Architecture,” Journal of Networking and Network Applications, vol.1, no.3, pp.88-102, 2021.

[23] J. Casas-Roma, J. Herrera-Joancomart¨ª and V.Torra, “k-Degree anonymity and edge selection: Improving data utility in large networks,” KNOWL INF SYST, vol.50, no.2, pp.447-474, 2017.

[24] R. Mortazavi and S. H. Erfani, “GRAM:An efficient (k, l) graph anonymization method,” EXPERT SYST APPL, vol.153, pp.1-9, 2020.

[25] W. Ren, K. Ghazinour and X. Lian, “kt-Safety: Graph Release via k-Anonymity and t-Closeness,” IEEE T KNOWL DATA EN, vol.35, no.9, pp.9102-9113, 2022.

[26] X. Ding, C. Wang, K. K. R. Choo and H. Jin, “A novel privacy preserving framework for large scale graph data publishing,” IEEE T KNOWL DATA EN, vol.33, no.2, pp.331-343, 2019.

[27] N. Yazdanjue, M. Fathian and B. Amiri, “Evolutionary algorithms for k- anonymity in social networks based on clustering approach,” The Computer Journal, vol.63, no.7, pp.1039-1062, 2020.

[28] Y. Tian, Z. Zhang, J. Xiong, L. Chen, J. Ma and C. Peng, “Achieving graph clustering privacy preservation based on structure entropy in social IoT,” IEEE INTERNET THINGS, vol.9, no.4, pp.2761-2777, 2021.

[29] P. Boldi, F. Bonchi, A. Gionis and T. Tassa, “Injecting uncertainty in graphs for identity obfuscation,” Proceedings of the VLDB Endowment, vol.5, no.11, pp.1376-1387, 2012.

[30] P. Mittal, C. Papamanthou and D. Song, “Preserving Link Privacy in Social Net-work Based Systems,” in Proceedings of 20th Annual Network and Distributed System Security Symposium, 2013, pp.1-10.

[31] H. H. Nguyen, A. Imine and M. Rusinowitch, “Anonymizing Social Graphs via Uncertainty Semantics,” in Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, 2015, pp.495-506.

[32] J. Hu, J. Yan, Z. Q. Wu, H. Liu and Y. H. Zhou, “A Privacy-Preserving Approach in Friendly-Correlations of Graph Based on Edge-Differential Privacy,” J INF SCI ENG, vol.35, no.4, pp.821-837, 2019.

[33] C. Dwork, “Differential Privacy,” in Proceedings of the 33rd Interna-tional Col-loquiium on Automata, Languages and Programming, 2006, pp.1-12.

[34] J. Xing and X. Ma, “DP-gSpan: A Pattern Growth-based Differentially Private Frequent Subgraph Mining Algorithm,” in Proceedings of 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), 2021, pp.397-404.

[35] X. Ding, S. Sheng, H. Zhou, X. Zhang, Z. Bao, P. Zhou and H. Jin, “Differ-entially private triangle counting in large graphs,” IEEE T KNOWL DATA EN, vol.34, no.11, pp.5278-5292, 2021.

[36] S. Lan, H. Xin, W. Yingjie, G. Yongyi, “Sensitivity reduction of degree histogram publication under node differential privacy via mean filtering,” CONCURR COMP-PRACT E, vol.33, no.8, pp.1-8, 2021.

[37] X. Jian, Y. Wang and L. Chen, “Publishing graphs under node differential privacy,” IEEE T KNOWL DATA EN, vol.35, no.4, pp.4164-4177, 2021.

[38] H. Huang, D. Zhang, F. Xiao, K. Wang, J. Gu and R. Wang, “Privacy-preserving Approach PBCN in Social Network with Differential Privacy,” IEEE TRANS NETW SERV, vol.17, no.2, pp.931-945, 2020.

[39] V. Karwa and A .B. Slavkovi¡¨ac, “Differentially private graphical degree sequences and synthetic graphs,” in Proceedings of International Con-ference on Privacy in Statistical Databases, 2012, pp.273-285.

[40] T. Gao and F. Li, “Sharing social networks using a novel differentially private graph model,” in Proceedings of 16th IEEE Annual Consumer Communications & Networking Conference, 2019, pp.1-4.

[41] J. Imola, T. Murakami and K. Chaudhuri, “Locally Differentially Private Analysis of Graph Statistics,” in Proceedings of 30th USENIX Security Symposium, 2021, pp.983¨C1000.