Hiding Individuals and Communities in a Social Network

Abstract

The Internet and social media have fueled enormous interest in social network analysis. New tools continue to be developed and used to analyse our personal connections, with particular emphasis on detecting communities or identifying key individuals in a social network. This raises privacy concerns that are likely to exacerbate in the future. With this in mind, we ask the question: Can individuals or groups actively manage their connections to evade social network analysis tools? By addressing this question, the general public may better protect their privacy, oppressed activist groups may better conceal their existence, and security agencies may better understand how terrorists escape detection. We first study how an individual can evade "network centrality" analysis without compromising his or her influence within the network. We prove that an optimal solution to this problem is hard to compute. Despite this hardness, we demonstrate that even a simple heuristic, whereby attention is restricted to the individual's immediate neighbourhood, can be surprisingly effective in practice. For instance, it could disguise Mohamed Atta's leading position within the WTC terrorist network, and that is by rewiring a strikingly-small number of connections. Next, we study how a community can increase the likelihood of being overlooked by community-detection algorithms. We propose a measure of concealment, expressing how well a community is hidden, and use it to demonstrate the effectiveness of a simple heuristic, whereby members of the community either "unfriend" certain other members, or "befriend" some non-members, in a coordinated effort to camouflage their community.

29 pages, 22 figures

References in corpus (4)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Statistical Mechanics of Community Detection
• New Online Ecology of Adversarial Aggregates: ISIS and beyond

Cited by in corpus (17)

• Adversarial Attack and Defense on Graph Data: A Survey
• Measuring Node Contribution to Community Structure with Modularity Vitality
• Adversarial Attack on Community Detection by Hiding Individuals
• Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN
• Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagation
• RobustECD: Enhancement of Network Structure for Robust Community Detection
• Multiplex Communities and the Emergence of International Conflict
• Can Large Language Models Improve the Adversarial Robustness of Graph Neural Networks?
• Structack: Structure-based Adversarial Attacks on Graph Neural Networks
• Single-Node Attacks for Fooling Graph Neural Networks
• Simple and Efficient Partial Graph Adversarial Attack: A New Perspective
• Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attacks
• Minimum Topology Attacks for Graph Neural Networks
• Node Copying: A Random Graph Model for Effective Graph Sampling
• Multidomain Evolutionary Optimization on Combinatorial Problems in Complex Networks
• RIDA: A Robust Attack Framework on Incomplete Graphs
• Social Diffusion Sources Can Escape Detection