Multiscale Evolutionary Perturbation Attack on Community Detection
arXiv:1910.09741
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 paper, 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 on attacking other community detection algorithms, validating its good transferability.
References in corpus (17)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Statistical Mechanics of Community Detection
- Finding local community structure in networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Detecting network communities by propagating labels under constraints
- Advanced modularity-specialized label propagation algorithm for detecting communities in networks
- Adversarial Attacks on Node Embeddings via Graph Poisoning
- Fast Gradient Attack on Network Embedding
- Multistep greedy algorithm identifies community structure in real-world and computer-generated networks