mlsanityData to 7 Oct 2026

Hiding Individuals and Communities in a Social Network

arXiv 1608.00375 ↗First posted 1 Aug 2016cs.SI physics.soc-phcited by 77

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 13; 2023: 15; 2024: 14; 2025: 17; 2026: 4.

77 papers.

Sort:

By area:

  1. 2021Robustness of Graph Neural Networks at Scalecited by 100
  2. 2021Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classificationcited by 79
  3. 2021Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learningcited by 44
  4. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  5. 2022Spectral Augmentation for Self-Supervised Learning on Graphscited by 38
  6. 2022Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNNcited by 34
  7. 2022On the Robustness of Graph Neural Diffusion to Topology Perturbationscited by 30
  8. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  9. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  10. 2022Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagationcited by 25
  11. 2023Adversarial Robustness in Graph Neural Networks: A Hamiltonian Approachcited by 24
  12. 2024Can Large Language Models Improve the Adversarial Robustness of Graph Neural Networks?cited by 22
38 more
  1. 2022Adversarial Weight Perturbation Improves Generalization in Graph Neural Networkscited by 21
  2. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  3. 2021Graph Structural Attack by Perturbing Spectral Distancecited by 16
  4. 2023Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debiascited by 16
  5. 2024Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FRONDcited by 16
  6. 2022GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networkscited by 14
  7. 2021CogDL: A Comprehensive Library for Graph Deep Learningcited by 12
  8. 2022Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networkscited by 12
  9. 2024A General Black-box Adversarial Attack on Graph-based Fake News Detectorscited by 11
  10. 2022Are Gradients on Graph Structure Reliable in Gray-box Attacks?cited by 10
  11. 2022Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guaranteescited by 9
  12. 2024Coupling Graph Neural Networks with Fractional Order Continuous Dynamics: A Robustness Studycited by 9
  13. 2021GraphAttacker: A General Multi-Task GraphAttack Frameworkcited by 8
  14. 2021BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detectioncited by 8
  15. 2021Structack: Structure-based Adversarial Attacks on Graph Neural Networkscited by 8
  16. 2023Simple and Efficient Partial Graph Adversarial Attack: A New Perspectivecited by 8
  17. 2023Deceptive Fairness Attacks on Graphs via Meta Learningcited by 6
  18. 2024Minimum Topology Attacks for Graph Neural Networkscited by 6
  19. 2021Adversarial Attacks on Graph Classification via Bayesian Optimisationcited by 5
  20. 2023HyperAttack: Multi-Gradient-Guided White-box Adversarial Structure Attack of Hypergraph Neural Networkscited by 5
  21. 2021Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attackscited by 4
  22. 2022Node Copying: A Random Graph Model for Effective Graph Samplingcited by 4
  23. 2023Spectral-Aware Augmentation for Enhanced Graph Representation Learningcited by 4
  24. 2024SAGMAN: Stability Analysis of Graph Neural Networks on the Manifoldscited by 4
  25. 2024Hypergraph Attacks via Injecting Homogeneous Nodes into Elite Hyperedgescited by 4
  26. 2026Are LLM-Enhanced Graph Neural Networks Robust against Poisoning Attacks?cited by 4
  27. 2023A Fast Algorithm for Moderating Critical Nodes via Edge Removalcited by 3
  28. 2024Three Revisits to Node-Level Graph Anomaly Detection: Outliers, Message Passing and Hyperbolic Neural Networkscited by 3
  29. 2021Hide and Seek: Outwitting Community Detection Algorithmscited by 2
  30. 2022What Does the Gradient Tell When Attacking the Graph Structurecited by 2
  31. 2023Everything Perturbed All at Once: Enabling Differentiable Graph Attackscited by 2
  32. 2023Evading Community Detection via Counterfactual Neighborhood Searchcited by 2
  33. 2024Debiased Graph Poisoning Attack via Contrastive Surrogate Objectivecited by 2
  34. 2025Influence Functions for Edge Edits in Non-Convex Graph Neural Networkscited by 2
  35. 2025RoBCtrl: Attacking GNN-Based Social Bot Detectors via Reinforced Manipulation of Bots Control Interactioncited by 2
  36. 2021Graphfool: Targeted Label Adversarial Attack on Graph Embeddingcited by 1
  37. 2021Adversarial Robustness of Probabilistic Network Embedding for Link Predictioncited by 1
  38. 2022Detecting Topology Attacks against Graph Neural Networkscited by 1

50 most cited of 77 All 77 (JSON)