A clustering-based differential privacy protection algorithm for weighted social networks

Lei Zhang; Lina Ge; Lei Zhang; Lina Ge

doi:10.3934/mbe.2024166

Mathematical Biosciences and Engineering

2024, Volume 21, Issue 3: 3755-3773. doi: 10.3934/mbe.2024166

Previous Article Next Article

Research article

A clustering-based differential privacy protection algorithm for weighted social networks

Lei Zhang ^1,2,
Lina Ge ^{1,2,3
,
,}

1.
School of Artificial Intelligence, Guangxi Minzu University, Nanning 530006, China
2.
Key Laboratory of Network Communication Engineering, Guangxi Minzu University, Nanning 530006, China
3.
Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Nanning 530006, China

Academic Editor: Yang Kuang

Received: 14 November 2023 Revised: 03 January 2024 Accepted: 23 January 2024 Published: 18 February 2024

Weighted social networks play a crucial role in various fields such as social media analysis, healthcare, and recommendation systems. However, with their widespread application and privacy issues have become increasingly prominent, including concerns related to sensitive information leakage, individual behavior analysis, and privacy attacks. Despite traditional differential privacy protection algorithms being able to protect privacy for edges with sensitive information, directly adding noise to edge weights may result in excessive noise, thereby reducing data utility. To address these challenges, we proposed a privacy protection algorithm for weighted social networks called DCDP. The algorithm combines the density clustering algorithm OPTICS to partition the weighted social network into multiple sub-clusters and adds noise to different sub-clusters at random sampling frequencies. To enhance the balance of privacy protection, we designed a novel privacy parameter calculation method. Through theoretical derivation and experimentation, the DCDP algorithm demonstrated its capability to achieve differential privacy protection for weighted social networks while effectively maintaining data accuracy. Compared to traditional privacy protection algorithms, the DCDP algorithm reduced the average relative error by approximately 20% and increases the proportion of unchanged shortest paths by about 10%. In summary, we aimed to address privacy issues in weighted social networks, providing an effective method to protect user-sensitive information while ensuring the accuracy and utility of data analysis.
- weighted social network,
- differential privacy,
- privacy protection,
- OPTICS algorithm
Citation: Lei Zhang, Lina Ge. A clustering-based differential privacy protection algorithm for weighted social networks[J]. Mathematical Biosciences and Engineering, 2024, 21(3): 3755-3773. doi: 10.3934/mbe.2024166

Related Papers:

Abstract

Weighted social networks play a crucial role in various fields such as social media analysis, healthcare, and recommendation systems. However, with their widespread application and privacy issues have become increasingly prominent, including concerns related to sensitive information leakage, individual behavior analysis, and privacy attacks. Despite traditional differential privacy protection algorithms being able to protect privacy for edges with sensitive information, directly adding noise to edge weights may result in excessive noise, thereby reducing data utility. To address these challenges, we proposed a privacy protection algorithm for weighted social networks called DCDP. The algorithm combines the density clustering algorithm OPTICS to partition the weighted social network into multiple sub-clusters and adds noise to different sub-clusters at random sampling frequencies. To enhance the balance of privacy protection, we designed a novel privacy parameter calculation method. Through theoretical derivation and experimentation, the DCDP algorithm demonstrated its capability to achieve differential privacy protection for weighted social networks while effectively maintaining data accuracy. Compared to traditional privacy protection algorithms, the DCDP algorithm reduced the average relative error by approximately 20% and increases the proportion of unchanged shortest paths by about 10%. In summary, we aimed to address privacy issues in weighted social networks, providing an effective method to protect user-sensitive information while ensuring the accuracy and utility of data analysis.

References

[1]	J. Su, Y. Cao, Y. Chen, Y, Liu, J. Song, Privacy protection of medical data in social network, BMC Med. Inf. Decis. Making, 21 (2021), 286. https://doi.org/10.1186/s12911-021-01645-0 doi: 10.1186/s12911-021-01645-0
[2]	X. Li, J. Yang, Z. Sun, J. Zhang, Differential privacy for edge weights in social networks, Secur. Commun. Netw., 2017 (2017), 4267921. https://doi.org/10.1155/2017/4267921 doi: 10.1155/2017/4267921
[3]	Q. Yuan, F. Yan, Z. Wen, Z. Zhang, Research on social network differential privacy protection algorithm based on spectral clustering (in Chinese), Comput. Eng. Sci., 44 (2022), 251–256. https://doi.org/10.3969/j.issn.1007-130X.2022.02.009 doi: 10.3969/j.issn.1007-130X.2022.02.009
[4]	C. Dwork, Differential privacy, in International Colloquium on Automata, Languages, and Programming, Springer, 2 (2006), 1–12. https://doi.org/10.1007/11787006_1
[5]	H. Jiang, J. Pei, D. Yu, J. Yu, B. Gong, X. Cheng, Applications of differential privacy in social network analysis: A survey, IEEE Trans. Knowl. Data Eng., 35 (2021), 108–127. https://doi.org/10.1109/TKDE.2021.3073062 doi: 10.1109/TKDE.2021.3073062
[6]	B. Ning, Y. Sun, X. Tao, G. Li, Differential privacy protection on weighted graph in wireless networks, Ad Hoc Networks, 110 (2021), 102303. https://doi.org/10.1016/j.adhoc.2020.102303 doi: 10.1016/j.adhoc.2020.102303
[7]	L. Lan, S. Ju, Weighted social network privacy protection based on differential privacy (in Chinese), J. Commun., 36 (2015), 145–159.
[8]	D. Wang, S. Long, Differential privacy algorithm in privacy protection of weighted social networks (in Chinese), Comput. Eng., 45 (2019), 114–118. https://doi.org/10.19678/j.issn.1000-3428.0049695 doi: 10.19678/j.issn.1000-3428.0049695
[9]	H. Huang, D. Zhang, F. Xiao, K. Wang, J. Gu, R. Wang, Privacy-preserving approach PBCN in social network with differential privacy, IEEE Trans. Netw. Serv. Manage., 17 (2020), 931–945. https://doi.org/10.1109/TNSM.2020.2982555 doi: 10.1109/TNSM.2020.2982555
[10]	H. Xu, Y. Tian, Privacy protection of weighted social networks under differential privacy (in Chinese), J. Xidian Univ., 49 (2022), 17–25+34. https://doi.org/10.19665/j.issn1001-2400.2022.01.002 doi: 10.19665/j.issn1001-2400.2022.01.002
[11]	T. Wang, S. Long, H. Ding, Differential privacy protection algorithm for large-scale social networks (in Chinese), Comput. Eng. Design, 41 (2020), 1568–1574. https://doi.org/10.16208/j.issn1000-7024.2020.06.011 doi: 10.16208/j.issn1000-7024.2020.06.011
[12]	Q. Qian, Z. Li, P. Zhao, Publishing graph node strength histogram with edge differential privacy, in Database Systems for Advanced Applications, Springer, 10828 (2018), 75–91. https://doi.org/10.1007/978-3-319-91458-9_5
[13]	C. Xu, L. Zhu, Y. Liu, J. Guan, S. Yu, DP-LTOD: Differential privacy latent trajectory community discovering services over location-based social networks, IEEE Trans. Serv. Comput., 14 (2018), 1068–1083. https://doi.org/10.1109/TSC.2018.2855740 doi: 10.1109/TSC.2018.2855740
[14]	H. Kang, Y. Ji, S. Zhang, Enhanced privacy preserving for social networks relational data based on personalized differential privacy, Chin. J. Electron., 31 (2022), 741–751. https://doi.org/10.1049/cje.2021.00.274 doi: 10.1049/cje.2021.00.274
[15]	Z. Liu, Y. Dong, X. Zhao, B. Zhang, A dynamic social network data publishing algorithm based on differential privacy, J. Inf. Secur., 8 (2017), 328–338. https://doi.org/10.4236/jis.2017.84021 doi: 10.4236/jis.2017.84021
[16]	Z. Liu, S. Wang, B. Zhang, J. Sun, Differential privacy protection in social networks based on dynamic ε (in Chinese), J. Zhengzhou Univ. (Sci. Ed.), 51 (2019), 56–62. https://doi.org/10.13705/j.issn.1671-6841.2018262 doi: 10.13705/j.issn.1671-6841.2018262
[17]	R. Chen, B. C. M. Fung, P. S. Yu, Correlated network data publication via differential privacy, VLDB J., 23 (2014), 653–676. https://doi.org/10.1007/s00778-013-0344-8 doi: 10.1007/s00778-013-0344-8
[18]	Y. Long, X. Zhou, Y. Li, X. Zhang, B. Xing, DDPLA: A dynamic differential privacy algorithm for social network based on local community, J. Internet Technol., 24 (2023), 101–112. https://doi.org/10.53106/160792642023012401010 doi: 10.53106/160792642023012401010
[19]	F. Zhang, Z. Jiang, Privacy protection method for social networks based on DSNPP algorithm (in Chinese), Comput. Technol. Dev., 25 (2015), 152–155.
[20]	L. Hou, W. Ni, S. Zhang, N. Fu, D. Zhang, Wdt-SCAN: Clustering decentralized social graphs with local differential privacy, Comput. Secur., 125 (2023), 103036. https://doi.org/10.1016/j.cose.2022.103036 doi: 10.1016/j.cose.2022.103036
[21]	H. Lei, S. Li, H. Wang, A weighted social network publishing method based on diffusion wavelets transform and differential privacy, Multimedia Tools Appl., 81 (2022), 20311–20328. https://doi.org/10.1007/s11042-022-12726-1 doi: 10.1007/s11042-022-12726-1
[22]	F. D. McSherry, Privacy integrated queries: An extensible platform for privacy-preserving data analysis, in Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, (2009), 19–30. https://doi.org/10.1145/1559845.1559850
[23]	T. Lv, H. Li, Z. Tang, Publishing triangle counting histogram in social networks based on differential privacy, Secur. Commun. Netw., 2021 (2021), 7206179. https://doi.org/10.1155/2021/7206179 doi: 10.1155/2021/7206179
[24]	M. Newman, http://www-personal.umich.edu/~mejn/, and V. Krebs website.
[25]	D. E. Knut, S. GraphBase, A Platform for Combinatorial Computing, Addison-Wesley, Boston, USA, 1st edition, 2009.
[26]	W. W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33 (1977), 452–473. https://doi.org/10.1086/jar.33.4.3629752 doi: 10.1086/jar.33.4.3629752

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)