TY  - EJOU
AU  - Hao, Yuanjing 
AU  - Wang, Xuemin 
AU  - Chang, Liang 
AU  - Li, Long 
AU  - Zhang, Mingmeng 

TI  - A Dynamic Social Network Graph Anonymity Scheme with Community Structure Protection
T2  - Computers, Materials \& Continua

PY  - 2025
VL  - 82
IS  - 2
SN  - 1546-2226

AB  - Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate these attacks but are cumbersome, neglect dynamic protection of community structure, and lack precise utility measures. To address these challenges, we present a dynamic social network graph anonymity scheme with community structure protection (DSNGA-CSP), which achieves the dynamic anonymization process by incorporating community detection. First, DSNGA-CSP categorizes communities of the original graph into three types at each timestamp, and only partitions community subgraphs for a specific category at each updated timestamp. Then, DSNGA-CSP achieves intra-community and inter-community anonymization separately to retain more of the community structure of the original graph at each timestamp. It anonymizes community subgraphs by the proposed novel -composition method and anonymizes inter-community edges by edge isomorphism. Finally, a novel information loss metric is introduced in DSNGA-CSP to precisely capture the utility of the anonymized graph through original information preservation and anonymous information changes. Extensive experiments conducted on five real-world datasets demonstrate that DSNGA-CSP consistently outperforms existing methods, providing a more effective balance between privacy and utility. Specifically, DSNGA-CSP shows an average utility improvement of approximately 30% compared to TAKG and CTKGA for three dynamic graph datasets, according to the proposed information loss metric <i>IL</i>.
KW  - Dynamic social network graph; <i>k</i>-composition anonymity; community structure protection; graph publishing; security and privacy

DO  - 10.32604/cmc.2024.059201