Source-linked AI summary
Hiding Individuals and Communities in a Social Network
Marcin Waniek, Tomasz Michalak, Talal Rahwan, Michael Wooldridge
TL;DR
The paper asks whether individuals and communities can rewire social connections to evade social-network analysis, motivated by unresolved privacy exposure. It analyzes the computational difficulty of optimal concealment and proposes simple local heuristics for individuals and groups. Despite that hardness, the authors report that practical disguise is surprisingly easy, while generic analysis tools can be misled by strategic network changes.
Problem
The paper asks whether individuals or communities can proactively manage social connections to reduce exposure to network-analysis tools, addressing a question that has received little prior attention.
Method
The paper analyzes centrality concealment with influence recovery, community concealment with a proposed measure, and practical ROAM and DICE rewiring heuristics.
Results
Despite the hardness of optimal disguise, simple heuristics are surprisingly effective in practice for concealing individuals and communities.
Takeaways & Limitations
The findings chart limits of privacy protection and show that generic social-network analysis tools can be easily misled in security applications.
Takeaways & Limitations
The study leaves open how to hide relationships from link-prediction algorithms and evade Eigenvector centrality.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether individuals and communities can proactively rewire social connections to evade network-analysis tools, addressing unresolved privacy concerns. It studies centrality concealment for individuals and community concealment through simple connection changes.
- Motivation: Social-network analysis can expose private information, while existing legal, algorithmic, and market countermeasures remain limited.The paper links these concerns to increasing institutional collection and analysis of social connections.
- Research question: The paper asks whether individuals or communities can manage their connections to reduce exposure to network-analysis tools.It frames this as disguising network standing to escape detection.
- Individual concealment: For individuals, the study targets degree, closeness, and betweenness centrality while preserving influence through network rewiring.The individual strategy uses unfriending and introducing neighbors to one another.
- Community concealment: For communities, the study proposes a concealment measure and evaluates a heuristic that removes internal ties or adds ties to non-members.These coordinated changes aim to make the community more likely to be overlooked by detection algorithms.
2 The Model
The model defines two concealment objectives: reduce an individual’s centrality without sacrificing influence, and hide a target community by rewiring the network within a modification budget.
- Basic concepts: Centrality measures represent node importance through neighbors, average distance, and shortest paths, using degree, closeness, and betweenness.These measures respectively reward more neighbors, shorter distances, and more shortest paths through the node.
- First objective: The individual objective lowers a source node’s three centrality measures without compromising its influence under established propagation models.The process divides the budget between centrality minimization and influence recovery.
- First objective: Influence recovery is evaluated either for every target node or for the source’s total influence across all nodes.These are the individual influence recovery and global influence recovery variants.
- Second objective: The community objective rewires a target subset so that community-detection algorithms do not return it as a community.The target community is considered exposed when it appears as an element of the resulting community structure.
3 Disguising Individuals
Optimal disguise is computationally difficult, but the ROAM heuristic restricts rewiring to an individual’s immediate neighborhood to reduce centrality while recovering influence.
- Hardness Results: All considered optimization problems are NP-complete except minimizing degree centrality.Optimal disguise may require complete network knowledge and modifications far from the source node.
- A Scalable Heuristic: ROAM targets practical use by restricting attention to the immediate neighborhood and requiring little computational power or technical expertise.Its name means Remove One, Add Many.
- A Scalable Heuristic: ROAM removes one edge from the source to a chosen neighbor, then connects that neighbor to up to b−1 other source neighbors.The rewiring stays within the source node’s local neighborhood.
- A Scalable Heuristic: Removing the source’s edge to a neighbor lowers or preserves its centrality but can reduce direct influence over that neighbor.Adding indirect connections is intended to compensate for the lost influence while increasing neighbors’ degrees.
4 Disguising Communities
The paper measures community concealment by how widely target members are distributed and how much they blend with non-members, then uses DICE to alter both kinds of structure.
- A Measure of Concealment: Target members may be spread across multiple detected communities, so concealment need not require the target subset to appear as one detected community.The paper treats the target community broadly as a subset of nodes.
- A Measure of Concealment: µ′ measures how widely the target members are distributed across communities, with larger values indicating greater concealment.Its numerator grows with the number of communities containing target members.
- A Measure of Concealment: µ′′ measures how well target members are hidden among non-members in the same detected communities, with larger values indicating greater concealment.The measure increases with the number of co-occurring non-members.
- A Measure of Concealment: The combined concealment measure µ uses α to control the trade-off between µ′ and µ′′.The parameter satisfies α ∈[0, 1].
- A Scalable Heuristic: DICE is a practical heuristic that disconnects members internally and connects them externally to camouflage the target community.It is designed for users with limited technical expertise or network-topology knowledge.
- A Scalable Heuristic: DICE reduces internal density and increases external connections, following the structure favored by modularity-based community detection.In practice, members can unfriend one another and send friendship requests to non-members.
5 Experiments
The experiments evaluate ROAM for disguising individuals and DICE for concealing communities across terrorist, social, and randomly generated networks. ROAM lowers source-node centrality rankings, while DICE hides communities with success that varies by detection algorithm and supports trade-offs between removed internal and added external links.
- ROAM: ROAM experiments use budgets of 2, 3, and 4, with source nodes selected by the lowest sum of degree, closeness, and betweenness rankings.Influence experiments use Independent Cascade activation probability 0.15 or uniformly distributed Linear Threshold thresholds.
- ROAM: ROAM decreases the source node’s centrality ranking, and larger rewiring budgets increase this effectiveness.Its influence impact varies with the network, influence model, and budget; budget 4 maintains or increases influence in 4 out of 6 cases.
- DICE: DICE repeatedly rewires a target community by removing d internal links and adding b−d links from members to non-members, then reruns community detection.Experiments use seven igraph community-detection algorithms and concealment measure µ with α = 0.5.
- DICE: DICE hides the target community with varying success across community-detection algorithms, while performance is not overly sensitive to d.This lets members trade off sacrificing real internal links against adding fake external links when concealment is insufficient.
- DICE: Figure 5 reports average concealment-measure µ values for b = 4 and d = 2 across algorithms and networks, using 50 simulations.Rows encode community-detection algorithms and networks, while cell colour intensity represents average µ.
6 Discussion
The paper argues that simple, locally executable rewiring heuristics can disguise individuals and communities despite computational hardness. It also identifies implications for privacy protection and security analysis, while noting that important evasion problems remain open.
- Discussion: Despite the hardness of finding optimal solutions, simple heuristics can make disguising individuals and communities surprisingly easy in practice.The authors describe these heuristics as readily implementable even by lay people.
- Implications: The findings chart practical limits for privacy protection and show that generic social network analysis tools can be easily misled in security applications.The paper therefore points toward specialized tools that account for link and node nature rather than topology alone.
- Open questions: Understanding how to evade social network analysis remains limited, including for link-prediction algorithms and Eigenvector centrality.These are identified as research questions that remain unanswered.
A Organization of the Appendix
The appendix defines the centrality measures and influence models, formulates the optimization problems, proves theoretical results, evaluates experiments, and studies constructing networks that conceal influential leaders.
- Appendix organization: The document first defines centrality measures and influence models before formulating the optimization problems.These definitions and formulations appear in Section B.
- Appendix organization: It then presents theoretical proofs, experimental results, and a network-construction study for hiding a leader’s identity while preserving high influence.The proof and experiment discussions are in Sections C and D, and network construction is in Section E.
B Definitions
This section defines network, centrality, influence, and community notation before formalizing two rewiring objectives: disguising an individual and concealing a community.
- Basic Notation: A network is represented as G=(V,E), with nodes V and edges E; paths, shortest paths, and distances provide the basic graph structure.The notation distinguishes directed from undirected networks and defines connectedness through paths between node pairs.
- Centrality Measures: Centrality measures quantify node importance through degree, closeness, and betweenness, respectively reflecting neighbours, average distance, and shortest paths.The formal treatment distinguishes centrality functions and directed versus undirected networks.
- Models of Influence: Influence propagates from an initially active seed set through discrete rounds under Independent Cascade or Linear Threshold models.Independent Cascade uses activation probabilities, whereas Linear Threshold activates nodes when active predecessors meet sampled thresholds; influence is the activation probability induced by a source.
- First Objective: Disguising a Node: The individual objective rewires a network within a budget to reduce a source node’s centrality and then recover its influence, with individual and global recovery variants.The formal problems constrain removable and addable edges and specify either per-node influence targets or a total influence target.
- Second Objective: Disguising a Community: The community objective rewires a target community within a budget, using a concealment measure where higher values indicate greater hiding in a detected community structure.The target structure is a disjoint partition, and the optimization seeks added and removed edges producing a community structure with increased concealment.
C Proofs
The paper proves computational hardness for disguising closeness and betweenness centrality and for recovering influence under two propagation models. The closeness result is established through reductions from Hamiltonian cycle, while influence recovery is linked to Set Cover.
- Disguising closeness centrality is NP-complete.
- The closeness reduction constructs auxiliary nodes and edges so that feasible disguising corresponds to a Hamiltonian cycle in the original network.
- Hamiltonian cycle existence is equivalent to reducing v†’s closeness centrality to q within the constructed edge-removal budget.
- Disguising betweenness centrality is NP-complete.
- Both global and individual influence recovery problems are NP-hard under the Independent Cascade model.
- Both global and individual influence recovery problems are NP-hard under the Linear Threshold model.
D.1 Configuring the ROAM Heuristic
ROAM chooses which neighbor to disconnect from v† and which b−1 neighbors to reconnect through it, with experiments comparing high- and low-degree choices. No setting dominates, but ROAM-max-min(3) performs best overall and is used thereafter.
- ROAM compares choosing v0 and the redirected neighbors by either their fewest or their most connections.
- ROAM-max-min(3) achieves the best overall performance among the tested settings, although no setting dominates all others.
- Subsequent ROAM experiments choose v0 as v†’s most-connected neighbor and connect it to the b−1 least-connected neighbors.
- Figure 13 evaluates repeated ROAM executions on 50 randomly generated 100-node scale-free networks with 3 edges added per generation step.
- For directed networks, ROAM selects v0 among v†’s successors because removing a successor reduces closeness centrality, unlike removing a predecessor.
D.2 Experimental Results
The experiments use anonymized Facebook, Twitter, and Google+ network fragments, including both undirected and directed networks. The ROAM results are reported in Figures 16–18.
- Experiments use anonymized Facebook, Twitter, and Google+ fragments from SNAP, with Twitter and Google+ providing the directed networks.
- Facebook fragments contain 61, 333, and 786 nodes, with 272, 2523, and 14027 edges, respectively, across small, medium, and large sizes.
- Twitter fragments contain 201, 247, and 235 nodes, with 2503, 8041, and 15957 edges, respectively, across small, medium, and large sizes.
- Google+ fragments contain 108, 215, and 338 nodes, with 2884, 7132, and 12341 edges, respectively, across small, medium, and large sizes.
- ROAM heuristic results are presented in Figures 16, 17, and 18.
E Constructing a Network from Scratch
The paper constructs Lieutenant networks from scratch so a source node retains influence while lieutenants outrank it on standard centrality measures. Theoretical conditions guarantee this concealment, while experiments reveal trade-offs among disguise and influence as network parameters vary.
- Network construction: A Lieutenant network is designed with a source connected to two groups of k lieutenants, cross-group lieutenant links, and members connected to c lieutenants in each group.The remaining n−2k−1 nodes are members, and lieutenant degrees differ by at most 1.
- Network construction: The source contacts only lieutenants, which are intended to outrank it on degree, closeness, and betweenness while passing its influence to members.Figure 14 illustrates the structure for c = 2.
- Empirical trade-offs: For 400-node networks, varying k and c produces four regimes with different combinations of centrality disguise and Independent-Cascade or Linear-Threshold influence.Figure 15 uses k on the x-axis and c on the y-axis, showing centrality differences and the source’s influence value.
- Empirical trade-offs: Small k with large c favors degree and closeness disguise plus Independent-Cascade influence, whereas large k with small c favors Linear-Threshold influence but weak disguise.The other parameter regimes likewise trade off betweenness disguise and the two influence models.
- Open direction: Future work remains to find network structures that disguise the source on all three centrality measures while maintaining high influence under both models.