GA Based Q-Attack on Community Detection

Abstract

Community detection plays an important role in social networks, since it can help to naturally divide the network into smaller parts so as to simplify network analysis. However, on the other hand, it arises the concern that individual information may be over-mined, and the concept community deception thus is proposed to protect individual privacy on social networks. Here, we introduce and formalize the problem of community detection attack and develop efficient strategies to attack community detection algorithms by rewiring a small number of connections, leading to individual privacy protection. In particular, we first give two heuristic attack strategies, i.e., Community Detection Attack (CDA) and Degree Based Attack (DBA), as baselines, utilizing the information of detected community structure and node degree, respectively. And then we propose a Genetic Algorithm (GA) based Q-Attack, where the modularity Q is used to design the fitness function. We launch community detection attack based on the above three strategies against three modularity based community detection algorithms on two social networks. By comparison, our Q-Attack method achieves much better attack effects than CDA and DBA, in terms of the larger reduction of both modularity Q and Normalized Mutual Information (NMI). Besides, we find that the adversarial networks obtained by Q-Attack on a specific community detection algorithm can be still effective on others, no matter whether they are modularity based or not, indicating its strong transferability.

arXiv comment11 pages, 7 figures; Corresponding author and date of submission added for v2; Word "simplify" corrected for v3; v4 is the newest version accepted by TCSS

References in corpus (19)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Finding community structure in very large networks
• 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
• Near linear time algorithm to detect community structures in large-scale networks
• Community detection algorithms: a comparative analysis
• Attack vulnerability of complex networks
• Robustness of community structure in networks
• Community Detection in Complex Networks Using Genetic Algorithms
• Multiresolution community detection for megascale networks by information-based replica correlations
• Adversarial Attacks on Node Embeddings via Graph Poisoning
• Adversarial Attack on Graph Structured Data
• Fast Gradient Attack on Network Embedding
• Efficiency of attack strategies on complex model and real-world networks
• Target Defense Against Link-Prediction-Based Attacks via Evolutionary Perturbations