@article{Hao2025, 
author = {Yuanjing Hao and Xuemin Wang and Liang Chang and Long Li and Mingmeng Zhang},
title = {A Dynamic Social Network Graph Anonymity Scheme with Community Structure Protection},
year = {2025},
journal = {Computers, Materials & Continua},
volume = {82},
number = {2},
pages = {3131-3159},
keywords = {Dynamic social network graph, k-composition anonymity, community structure protection, graph publishing, security and privacy},
url = {https://www.sciopen.com/article/10.32604/cmc.2024.059201},
doi = {10.32604/cmc.2024.059201},
abstract = {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  k-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  k-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 IL.}
}