Evading Overlapping Community Detection via Proxy Node Injection
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915513804783616 |
|---|---|
| author | Loi, Dario Silvestri, Matteo Silvestri, Fabrizio Tolomei, Gabriele |
| author_facet | Loi, Dario Silvestri, Matteo Silvestri, Fabrizio Tolomei, Gabriele |
| contents | Protecting privacy in social graphs requires preventing sensitive information, such as community affiliations, from being inferred by graph analysis, without substantially altering the graph topology. We address this through the problem of \emph{community membership hiding} (CMH), which seeks edge modifications that cause a target node to exit its original community, regardless of the detection algorithm employed. Prior work has focused on non-overlapping community detection, where trivial strategies often suffice, but real-world graphs are better modeled by overlapping communities, where such strategies fail. To the best of our knowledge, we are the first to formalize and address CMH in this setting. In this work, we propose a deep reinforcement learning (DRL) approach that learns effective modification policies, including the use of proxy nodes, while preserving graph structure. Experiments on real-world datasets show that our method significantly outperforms existing baselines in both effectiveness and efficiency, offering a principled tool for privacy-preserving graph modification with overlapping communities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21211 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Evading Overlapping Community Detection via Proxy Node Injection Loi, Dario Silvestri, Matteo Silvestri, Fabrizio Tolomei, Gabriele Social and Information Networks Artificial Intelligence I.2.6; I.2.8; G.2.2; I.5.1 Protecting privacy in social graphs requires preventing sensitive information, such as community affiliations, from being inferred by graph analysis, without substantially altering the graph topology. We address this through the problem of \emph{community membership hiding} (CMH), which seeks edge modifications that cause a target node to exit its original community, regardless of the detection algorithm employed. Prior work has focused on non-overlapping community detection, where trivial strategies often suffice, but real-world graphs are better modeled by overlapping communities, where such strategies fail. To the best of our knowledge, we are the first to formalize and address CMH in this setting. In this work, we propose a deep reinforcement learning (DRL) approach that learns effective modification policies, including the use of proxy nodes, while preserving graph structure. Experiments on real-world datasets show that our method significantly outperforms existing baselines in both effectiveness and efficiency, offering a principled tool for privacy-preserving graph modification with overlapping communities. |
| title | Evading Overlapping Community Detection via Proxy Node Injection |
| topic | Social and Information Networks Artificial Intelligence I.2.6; I.2.8; G.2.2; I.5.1 |
| url | https://arxiv.org/abs/2509.21211 |