# Hiding Individuals and Communities in a Social Network

arXiv: https://arxiv.org/abs/1608.00375 · HTML: https://mlsanity.com/paper/1608.00375/

## Key facts

- Cited by 77 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2016.

## Built on by (most cited first, 30 of 77)

- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification](https://mlsanity.com/paper/2110.14012/) (2021)
- [Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning](https://mlsanity.com/paper/2111.04314/) (2021)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Spectral Augmentation for Self-Supervised Learning on Graphs](https://mlsanity.com/paper/2210.00643/) (2022)
- [Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN](https://mlsanity.com/paper/2207.00012/) (2022)
- [On the Robustness of Graph Neural Diffusion to Topology Perturbations](https://mlsanity.com/paper/2209.07754/) (2022)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks](https://mlsanity.com/paper/2205.13892/) (2022)
- [Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagation](https://mlsanity.com/paper/2201.07986/) (2022)
- [Adversarial Robustness in Graph Neural Networks: A Hamiltonian Approach](https://mlsanity.com/paper/2310.06396/) (2023)
- [Can Large Language Models Improve the Adversarial Robustness of Graph Neural Networks?](https://mlsanity.com/paper/2408.08685/) (2024)
- [Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks](https://mlsanity.com/paper/2212.04983/) (2022)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND](https://mlsanity.com/paper/2404.17099/) (2024)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks](https://mlsanity.com/paper/2201.12741/) (2022)
- [CogDL: A Comprehensive Library for Graph Deep Learning](https://mlsanity.com/paper/2103.00959/) (2021)
- [Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks](https://mlsanity.com/paper/2209.05957/) (2022)
- [A General Black-box Adversarial Attack on Graph-based Fake News Detectors](https://mlsanity.com/paper/2404.15744/) (2024)
- [Are Gradients on Graph Structure Reliable in Gray-box Attacks?](https://mlsanity.com/paper/2208.05514/) (2022)
- [BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detection](https://mlsanity.com/paper/2106.09989/) (2021)
- [Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees](https://mlsanity.com/paper/2205.03546/) (2022)
- [Coupling Graph Neural Networks with Fractional Order Continuous Dynamics: A Robustness Study](https://mlsanity.com/paper/2401.04331/) (2024)
- [GraphAttacker: A General Multi-Task GraphAttack Framework](https://mlsanity.com/paper/2101.06855/) (2021)
- [Structack: Structure-based Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2107.11327/) (2021)
- [Simple and Efficient Partial Graph Adversarial Attack: A New Perspective](https://mlsanity.com/paper/2308.07834/) (2023)
- [Deceptive Fairness Attacks on Graphs via Meta Learning](https://mlsanity.com/paper/2310.15653/) (2023)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)

## Abstract (arXiv)

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.