PaperlayerView exact revision on arXiv

Source-linked AI summary

GA Based Q-Attack on Community Detection

Jinyin Chen, Lihong Chen, Yixian Chen, Minghao Zhao, Shanqing Yu, Qi Xuan, Xiaoniu Yang

arXiv:1811.00430v4cs.SI

TL;DR

Community detection can expose personal information, motivating attacks that make communities harder to detect. The paper formalizes this attack problem and proposes heuristic strategies and GA-based Q-Attack, which uses modularity Q as its fitness function. Q-Attack outperforms the heuristics in most considered white-box cases and transfers to effective black-box attacks.

  • Problem

    Community detection can over-mine personal information, while prior community-hiding work targeted selected nodes or communities rather than making overall community structure harder to detect.

    Source: §I · p. 1, C. Researches on Anti-Detection of… · p. 3

  • Method

    The paper formalizes community detection attack and proposes two heuristic strategies and GA-based Q-Attack, which uses modularity Q as its fitness function.

    Source: §I · pp. 1–2, B. GA Based Q-Attack · p. 5

  • Results

    Q-Attack outperformed CDA and DBA in almost all considered white-box cases and showed transferability to effective black-box attacks; at T limited to 5%, its relative reductions of Q and NMI were about 2 to 3 times those for the optimal heuristic on average.

    Source: §V · p. 10, D. Experimental Results · p. 10

  • Takeaways & Limitations

    The authors suggest community detection attack can serve as a robust evaluation metric for comparing algorithms' anti-attack capacity.

    Source: §I · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper frames community detection attacks as a response to privacy risks from over-mining and proposes heuristic and GA-based strategies to make detection less effective. It situates this work among community detection methods that use modularity, network spectra, labels, information theory, and other approaches.

I. INTRODUCTION

  • Community detection helps reveal network organization and functions, and has been widely studied across network-science applications.The introduction names link prediction, node classification, and network reconstruction alongside community detection.Source: §I · p. 1
  • Community detection can reveal personal information, motivating attacks that alter network structure to reduce detection performance and help protect privacy.The paper presents attack strategies as potential guidance for disguising social circles and changing interactions.Source: §I · p. 1
  • Q-Attack treats attack-scheme search under a given cost as combinatorial optimization, using modularity Q as its fitness function.The paper also motivates degree-based targeting because degree uses local information and requires less computation than betweenness.Source: §I · p. 1
  • The paper formalizes community detection attack and proposes two heuristics plus GA-based Q-Attack, with experiments comparing strategies across detection algorithms and real-world networks.It also reports validating Q-Attack's transferability and suggests attacks could evaluate algorithms' anti-attack capacity.Source: §I · p. 2

A. Community Detection Algorithms

  • The reviewed community-detection approaches include modularity optimization and spectral clustering, as well as label propagation, Infomap, and Potts-model methods.Examples include Blondel et al.'s two-level modularity optimization and Infomap's optimization of average description length.Source: A. Community Detection Algorithms · p. 2

B. Attacks on Complex Networks

Earlier work studied network vulnerability, adversarial attacks on network algorithms, and methods for hiding selected communities. This paper addresses a broader attack objective: changing a small number of links to make community structure harder to detect overall.

B. Attacks on Complex Networks

  • Prior network-attack studies examined structural vulnerability, link perturbations, and attacks on prediction, classification, and embedding algorithms.Examples include node or link removal, randomized link replacement, and adversarial graph modifications.Source: B. Attacks on Complex Networks · p. 2

III. METHODS

  • The framework combines an attack scheme with community-detection algorithms and evaluates attack effects using Q and NMI.The paper introduces heuristic and evolutionary attack strategies in the framework.Source: Figure 1 · p. 3, §III · p. 3

C. Researches on Anti-Detection of Community

  • Earlier privacy-focused methods hid selected nodes or communities, while this paper targets a global decrease in the quantification of detected communities through subtle network changes.The authors note that comparatively little attention had been paid to attacks that make community structure harder for algorithms to detect.Source: C. Researches on Anti-Detection of… · pp. 2–3

III. METHODS

  • The attack solution Eattack specifies link additions and removals that transform the original network into an adversarial network with unchanged nodes.The objective is for community-detection algorithms to produce lower-quality results on that modified network.Source: §III · p. 3

A. Heuristic Attack Strategy

The heuristic strategies use rewiring attacks, which preserve the target node’s degree. CDA uses detected community structure to weaken within-community ties and add cross-community ties, while DBA targets high-degree nodes.

A. Heuristic Attack Strategy

  • Rewiring deletes one existing link and adds one nonexistent link for a target node, preserving its degree while changing its connections.The paper describes this as a lower-cost, more concealed attack than removing and adding links involving four nodes.Source: A. Heuristic Attack Strategy · p. 3
  • CDA uses detected communities to select within-community links for deletion and cross-community non-links for addition.The strategy relies on the tendency of community structure to have denser within-community connections than between-community connections.Source: A. Heuristic Attack Strategy · p. 4
  • DBA targets nodes with large degrees, choosing them instead of CDA’s randomly selected target nodes.The remaining attack procedure is the same as CDA’s.Source: A. Heuristic Attack Strategy · pp. 4–5

B. GA Based Q-Attack

Q-Attack uses a genetic algorithm to search for rewiring schemes, with modularity guiding fitness. Its population evolves through selection and genetic operators while respecting link-conflict constraints.

B. GA Based Q-Attack

  • Q-Attack uses a genetic algorithm to search for effective rewiring attack schemes through an evolving population of candidate solutions.Individuals with better fitness have more chances to survive and multiply; crossover and mutation generate offspring.Source: B. GA Based Q-Attack · p. 5
  • Each chromosome encodes a sequence of rewiring attacks, with its length representing the number of attacks.Each gene contains a deleted link and an added link.Source: B. GA Based Q-Attack · p. 5
  • The fitness function uses modularity, giving lower-modularity individuals larger fitness to search for partitions with reduced modularity.The attack is evaluated on the partition produced by the specified community detection algorithm.Source: B. GA Based Q-Attack · p. 5
  • Roulette-wheel selection makes mating probability proportional to fitness, while initialization avoids repeated link additions or deletions.The initial population is fixed in size, and each individual represents a combination of rewiring attacks.Source: B. GA Based Q-Attack · p. 5
  • Single-point crossover, three equally probable mutation operators, and elitist replacement maintain variation and retain high-fitness individuals.Mutation can change a deleted link, change an added link, or replace a gene; the worst 10% of offspring are replaced by the best 10% of parents.Source: B. GA Based Q-Attack · p. 6
  • The algorithm stops after a fixed number of generations, with crossover and mutation subject to feasibility checks against link conflicts.The process also uses elitism to preserve high-fitness parent individuals.Source: B. GA Based Q-Attack · p. 6

A. Datasets

The experiments use four real-world networks with stated ground-truth community partitions, spanning small social networks and larger networks of teams or books.

A. Datasets

  • The Zachary karate club network has 34 nodes and 78 links, divided into two groups following conflict between the instructor and administrator.Source: A. Datasets · p. 6
  • The bottlenose dolphin network has 62 nodes and 159 links, with the dolphins divided into two groups.Source: A. Datasets · p. 6
  • The American college football network contains 115 teams connected by matches from one season, with teams assigned to 12 communities.The network has 613 links.Source: A. Datasets · p. 6
  • The American political books network has 105 book nodes and 441 links, with books divided into three categories by political stance.A link indicates that the books were purchased by the same consumer.Source: A. Datasets · p. 6

B. Community Detection Algorithms

The paper attacks six algorithms that mainly detect non-overlapping communities, spanning modularity optimization, label propagation, information-flow compression, and embedding-based clustering.

B. Community Detection Algorithms

C. Metrics for Community Structure •

The section uses modularity to measure network-community division and Normalized Mutual Information (NMI) to assess the similarity of partitions. NMI addresses a weakness of mutual information alone when clusters are split.

C. Metrics for Community Structure •

  • Modularity Q measures the difference between the actual fraction of within-community links and the expected fraction under random connections.The paper also describes it as a measure of network-division quality, especially when community structure is unknown.Source: C. Metrics for Community Structure • · p. 7
  • NMI assesses clustering quality by measuring the similarity between two partitions using normalized mutual information.The mutual information is defined as the relative entropy between the joint distribution and the product of the marginal distributions.Source: C. Metrics for Community Structure • · p. 7
  • NMI addresses the problem that mutual information alone gives the same value when clusters in one partition are split into smaller clusters.Source: C. Metrics for Community Structure • · p. 7
  • An NMI value of 1 means the two partitions are identical; larger values indicate greater similarity.Source: C. Metrics for Community Structure • · p. 7

D. Experimental Results

Across six algorithms and four networks, Q-Attack generally reduces both modularity Q and NMI more than the heuristic strategies, with a larger relative advantage at smaller attack budgets. Experiments also examine attacks across algorithms and networks, including a four-rewiring illustration on Karate.

D. Experimental Results

  • The experiments vary attack number; heuristic target sets are five nodes for Karate and six for Dolphins, while Q-Attack uses population size 100 and 500 generations.For FN on Dolphins at T=4, the selected rates are Pc=0.6 and Pm=0.06; reported means use 50 adversarial networks for heuristics and 10 Q-Attack runs for T=2–8.Source: D. Experimental Results · pp. 7–8
  • For T=1, the study obtains results by checking all possible situations, noting that the two networks are small enough to make this practical.Source: D. Experimental Results · pp. 8–9
  • At 5% attack budget, Q-Attack’s relative reductions of Q and NMI average about 2–3 times those of the optimal heuristic; at 2%, they reach 5 times or more.The comparison covers Karate and Dolphins at 5% of links and Football and Polbooks at 2%; the exception is NMI reduction for Football under Infomap.Source: Table II · p. 9, D. Experimental Results · pp. 9–10
  • Across Karate and Dolphins, Q-Attack reduces Q and NMI more sharply than the other strategies, while DBA usually reduces Q more than CDA and CDA usually reduces NMI more than DBA.Figs. 5 and 6 compare four attack strategies across three detection algorithms and varying attack numbers on the two networks.Source: Figure 5 · p. 8, Figure 6 · p. 8, D. Experimental Results · p. 9
  • On Karate under Louvin, four rewiring attacks reduce Q from 0.4188 to 0.3053 and NMI from 0.5866 to 0.3078, while detected communities increase from four to five.Fig. 7 contrasts detected communities before and after attack; node colors show detected communities and shapes show given labels.Source: D. Experimental Results · p. 10, Figure 7 · p. 10

E. Transferability of Q-Attack

Q-Attack’s adversarial networks retain considerable attack effects on other detection algorithms in most cases. Transfer effects occur more frequently for networks generated against Louvain and Infomap, though those algorithms show relative robustness to transferred attacks.

E. Transferability of Q-Attack

  • Because the target algorithm may be unknown, the authors test transferability by applying networks generated against particular algorithms to others and report relative Q reductions in Table III.Source: E. Transferability of Q-Attack · p. 10
  • Adversarial networks generated against specific detection algorithms retain considerable attack effects on others in most cases.Source: E. Transferability of Q-Attack · p. 10
  • Networks generated against Louvain and Infomap show significant transfer effects more frequently across other algorithms.Source: E. Transferability of Q-Attack · p. 10
  • Louvain and Infomap show relatively small Q reductions in most cases when attacked by transferred networks, except when attacked directly.The authors suggest that attacks on better-performing algorithms may yield stronger transferability.Source: E. Transferability of Q-Attack · p. 10

V. CONCLUSION

Across four well-known social networks, the proposed attacks often reduce detection performance by lowering modularity Q and NMI after disturbing only a small number of connections. Q-Attack generally outperforms CDA and DBA in white-box cases and also shows transferability to other algorithms.

V. CONCLUSION

  • Q-Attack outperforms CDA and DBA in almost all white-box cases and also enables effective black-box attacks on many other algorithms.Source: §V · p. 10
  • The attack strategies often partly impair detection by reducing modularity Q and NMI after disturbing only a small number of connections.Source: §V · p. 10
  • The authors conclude that Q-Attack can feasibly be used to protect privacy against community detection.Source: §V · p. 10
  • The study uses only modularity Q for simplicity, seeks more efficient strategies for larger networks, and mainly considers non-overlapping communities; overlapping cases remain an extension.Source: §V · pp. 10–11
Loading 1811.00430v4…