MLDA: a multi-level <i>k</i>-degree anonymity scheme on directed social network graphs

doi:10.1007/s11704-023-2759-8

Front. Comput. Sci.

2024, Vol. 18

Issue (2) : 182814 https://doi.org/10.1007/s11704-023-2759-8

Information Security

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

Yuanjing HAO¹, Long LI^1,², Liang CHANG¹(

), Tianlong GU²

¹. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China
². Engineering Research Center of Trustworthy AI (Ministry of Education), Jinan University, Guangzhou 510632, China

Download: PDF(10797 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

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

Corresponding Author(s): Liang CHANG

About author:

Peng Lei and Charity Ngina Mwangi contributed equally to this work.

Just Accepted Date: 02 August 2023 Issue Date: 17 November 2023

Cite this article:

Yuanjing HAO,Long LI,Liang CHANG, et al. MLDA: a multi-level k-degree anonymity scheme on directed social network graphs[J]. Front. Comput. Sci., 2024, 18(2): 182814.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-2759-8
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I2/182814

Fig.1 The flowchart of the MLDA scheme

Fig.2 The mergence of a fake node pair

Fig.3 An example of graph modification

Tab.1 The statistics and properties of datasets

Fig.4 Average convergent attractiveness at different percentages

Fig.5 Comparison of

E r r o r_r a t e

of graph analysis metrics on Email-Eu-core dataset

Fig.6 Comparison of

E r r o r_r a t e

of graph analysis metrics on Polblogs dataset

Fig.7 Comparison of

E r r o r_r a t e

of graph analysis metrics on soc-wiki-Vote dataset

Fig.8 Comparison of

E r r o r_r a t e

of graph analysis metrics on CiteSeer dataset

Fig.9 Average

E r r o r_r a t e

of graph analysis metrics on all datasets

Fig.10 Comparison results of community structure metrics on Email-Eu-core dataset

Fig.11 Comparison results of community structure metrics on Polblogs dataset

Fig.12 Comparison results of community structure metrics on soc-wiki-Vote dataset

Fig.13 Comparison results of community structure metrics on CiteSeer dataset

Fig.14 Average of community structure metrics on all datasets

Fig.15 Comparison results of Shannon entropy metric on four datasets

1	F, Ferri P, Grifoni T Guzzo . New forms of social and professional digital relationships: the case of facebook. Social Network Analysis and Mining, 2012, 2( 2): 121–137
2	D, Yang B, Qu P Cudré-Mauroux . Privacy-preserving social media data publishing for personalized ranking-based recommendation. IEEE Transactions on Knowledge and Data Engineering, 2019, 31( 3): 507–520
3	R K, Langari S, Sardar S A A, Mousavi R Radfar . Combined fuzzy clustering and firefly algorithm for privacy preserving in social networks. Expert Systems with Applications, 2020, 141: 112968
4	X, Wang Y Li . Geo-social network publication based on differential privacy. Frontiers of Computer Science, 2018, 12( 6): 1264–1266
5	H, Huang D, Zhang F, Xiao K, Wang J, Gu R Wang . Privacy-preserving approach PBCN in social network with differential privacy. IEEE Transactions on Network and Service Management, 2020, 17( 2): 931–945
6	X, Jian Y, Wang L Chen . Publishing graphs under node differential privacy. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 4): 4164–4177
7	X, Pei X, Deng S, Tian K Xue . 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	S, Zhang W, Ni N Fu . Community preserved social graph publishing with node differential privacy. In: Proceedings of 2020 IEEE International Conference on Data Mining (ICDM). 2020, 1400−1405
9	J, Casas-Roma J, Herrera-Joancomartí V Torra . 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	T, Ji C, Luo Y, Guo Q, Wang L, Yu P Li . Community detection in online social networks: a differentially private and parsimonious approach. IEEE Transactions on Computational Social Systems, 2020, 7( 1): 151–163
13	F, Rousseau J, Casas-Roma M Vazirgiannis . Community-preserving anonymization of graphs. Knowledge and Information Systems, 2018, 54( 2): 315–343
14	L Sweeney . k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 2002, 10( 5): 557–570
15	M, Kiabod M N, Dehkordi B Barekatain . TSRAM: A time-saving k-degree anonymization method in social network. Expert Systems with Applications, 2019, 125: 378–396
16	M, Kiabod M N, Dehkordi B Barekatain . 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	J, Casas-Roma J, Herrera-Joancomartí V Torra . 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	X, Ding C, Wang K K R, Choo H Jin . A novel privacy preserving framework for large scale graph data publishing. IEEE Transactions on Knowledge and Data Engineering, 2019, 33( 2): 331–343
21	S H, Lin R Xiao . Towards publishing directed social network data with k-degree anonymization. Concurrency and Computation: Practice and Experience, 2022, 34( 24): e7226
22	J, Casas-Roma J, Salas F D, Malliaros M Vazirgiannis . 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	A T, Hoang B, Carminati E Ferrari . Time-aware anonymization of knowledge graphs. ACM Transactions on Privacy and Security, 2022, doi:
26	W L, Ren K, Ghazinour X Lian . kt-safety: Graph release via k-anonymity and t-closeness. IEEE Transactions on Knowledge and Data Engineering, 2022, 35( 9): 9102–9113
27	H, Zhang L, Lin L, Xu X Wang . Graph partition based privacy-preserving scheme in social networks. Journal of Network and Computer Applications, 2021, 195: 103214
28	R, Mortazavi S H Erfani . Gram: An efficient (k, l) graph anonymization method. Expert Systems with Applications, 2020, 153: 113454
29	R, Assam M, Hassani M, Brysch T Seidl . (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	C H, Tai P S, Yu D N, Yang M S Chen . 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	D K, Jain X, Ren D Jiang . A personalized α, β, l, k-anonymity model of social network for protecting privacy. Wireless Communications & Mobile Computing, 2022, 2022: 7187528
32	T, Ma Q, Liu J, Cao Y, Tian A, Al-Dhelaan M Al-Rodhaan . Lgiem: Global and local node influence based community detection. Future Generation Computer Systems, 2020, 105: 533–546
33	S, Kumar P Kumar . Upper approximation based privacy preserving in online social networks. Expert Systems with Applications, 2017, 88: 276–289
34	X, Zhang J, Li J, Liu H, Zhang L Liu . Social network sensitive area perturbance method based on firefly algorithm. IEEE Access, 2019, 7: 137759–137769
35	L, Jain R Katarya . Discover opinion leader in online social network using firefly algorithm. Expert Systems with Applications, 2019, 122: 1–15
36	X, Zhang J, Liu J, Li L Liu . 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	H, Yin A R, Benson J, Leskovec D F Gleich . Local higher-order graph clustering. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 555−564
38	L A, Adamic N Glance . 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	L, Danon A, Díaz-Guilera J, Duch A Arenas . Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005( 9): P09008
41	L, Hubert P Arabie . Comparing partitions. Journal of Classification, 1985, 2( 1): 193–218
42	S Dongen . Performance criteria for graph clustering and markov cluster experiments. Amsterdam: CWI (Centre for Mathematics and Computer Science), 2000
43	W M Rand . Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 1971, 66( 336): 846–850
44	I, Wagner D Eckhoff . Technical privacy metrics: a systematic survey. ACM Computing Surveys, 2019, 51( 3): 57

[1]

FCS-22759-OF-YH_suppl_1

Download

[1]	Yanni HAN, Deyi LI, Teng WANG. Identifying different community members in complex networks based on topology potential[J]. Front Comput Sci Chin, 2011, 5(1): 87-99.

Viewed

Full text

Abstract

Cited

Shared

Discussed