Multiscale Evolutionary Perturbation Attack on Community Detection
- 2 November 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Social Systems
- Vol. 8 (1) , 62-75
Abstract
Community detection, aiming to group nodes based on their connections, plays an important role in network analysis since communities, treated as meta-nodes, allow us to create a large-scale map of a network to simplify its analysis. However, for privacy reasons, we may want to prevent communities from being discovered in certain cases, leading to the topics on community deception. In this article, we formalize this community detection attack problem in three scales, including global attack (macroscale), target community attack (mesoscale), and target node attack (microscale). We treat this as an optimization problem and further propose a novel evolutionary perturbation attack (EPA) method, where we generate adversarial networks to realize the community detection attack. Numerical experiments validate that our EPA can successfully attack network community algorithms in all three scales, i.e., hide target nodes or communities and further disturb the community structure of the whole network by only changing a small fraction of links. By comparison, our EPA behaves better than a number of baseline attack methods on six synthetic networks and three real-world networks. More interestingly, although our EPA is based on the Louvain algorithm, it is also effective in attacking other community detection algorithms, validating its good transferability.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61502423, 61973273, 61572439, 62072406)
- Zhejiang Provincial Natural Science Foundation of China (LR19F030001, LY19F020025)
- Zhejiang science and technology plan project (LGF18F030009)
- Major Special Funding for Science and Technology Innovation 2025 in Ningbo (2018B10063)
- Ministry of Public Security’s Research Project “Research and Demonstration Application of Key Technologies of Criminal Social Network Model”
This publication has 39 references indexed in Scilit:
- Threshold Random Walkers for Community Structure Detection in Complex NetworksJournal of Software, 2013
- Detecting network communities by propagating labels under constraintsPhysical Review E, 2009
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Multistep greedy algorithm identifies community structure in real-world and computer-generated networksPhysical Review E, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences, 2008
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- Finding local community structure in networksPhysical Review E, 2005
- Functional cartography of complex metabolic networksNature, 2005
- Computing Communities in Large Networks Using Random Walks2005