Abstract
Our private connections can be exposed by link prediction algorithms. To date, this threat has only been addressed from the perspective of a central authority, completely neglecting the possibility that members of the social network can themselves mitigate such threats. We fill this gap by studying how an individual can rewire her own network neighborhood to hide her sensitive relationships. We prove that the optimization problem faced by such an individual is NP-complete, meaning that any attempt to identify an optimal way to hide one's relationships is futile. Based on this, we shift our attention towards developing effective, albeit not optimal, heuristics that are readily-applicable by users of existing social media platforms to conceal any connections they deem sensitive. Our empirical evaluation reveals that it is more beneficial to focus on "unfriending" carefully-chosen individuals rather than befriending new ones. In fact, by avoiding communication with just 5 individuals, it is possible for one to hide some of her relationships in a massive, real-life telecommunication network, consisting of 829,725 phone calls between 248,763 individuals. Our analysis also shows that link prediction algorithms are more susceptible to manipulation in smaller and denser networks. Evaluating the error vs. attack tolerance of link prediction algorithms reveals that rewiring connections randomly may end up exposing one's sensitive relationships, highlighting the importance of the strategic aspect. In an age where personal relationships continue to leave digital traces, our results empower the general public to proactively protect their private relationships.
Introduction
In the era of "big data," social footprints are rarely private. Link prediction algorithms—the technology behind features like "People You May Know"—analyze network topology to suggest new connections or uncover hidden ones. While beneficial for recommendations, these tools can be weaponized for "link re-identification attacks," where an observer infers sensitive relationships (e.g., political affiliations or whistleblower contacts) that users intentionally left undeclared.
Existing research typically assumes a "central authority" is responsible for anonymizing the entire graph. This study shifts the perspective to the individual user (the "evader"). The authors investigate whether a single person, with limited local knowledge of the network, can rewire their own neighborhood to successfully hide sensitive relationships from standard prediction algorithms.
Methods: Heuristics for Evasion
The authors first formalize the Evading Link Prediction problem, proving it is NP-complete for common similarity-based algorithms like the Jaccard index or Adamic-Adar. This complexity implies that finding a mathematically optimal set of modifications is computationally infeasible.
To address this, two practical heuristics requiring only local "ego network" knowledge were developed:
- Closed-Triad-Removal (CTR): This "unfriending" strategy involves removing links to mutual friends of the sensitive contact. By breaking closed triads, the evader significantly lowers the similarity score used by algorithms to predict a link.
- Open-Triad-Creation (OTC): This "befriending" strategy involves adding links to strangers (neighbors of neighbors) to create "open triads," attempting to dilute the relative importance of the sensitive connection.
Results: The Power of Strategic Unfriending
The effectiveness of these strategies was evaluated using both synthetic graphs and a massive European telecommunication network (829,725 calls among 248,763 individuals).
Key findings include:
- Unfriending is Superior: The CTR heuristic was consistently and significantly more effective than OTC. In the context of social privacy, "less is more."
- Strategy is Essential: Randomly modifying connections can backfire, potentially making a sensitive relationship more visible by accidentally highlighting the connection.
- Efficiency at Scale: In the massive telecom dataset, strategically avoiding communication with just five individuals effectively hid sensitive relationships.
- Metric Decline: Strategic CTR caused a sharp decline in Area Under the ROC Curve (AUC) and Average Precision (AP), indicating that prediction algorithms became much less likely to flag hidden links.
Conclusion and Future Directions
While these heuristics empower users to protect their privacy, several challenges remain. If a seeker has access to historical network snapshots, the sudden removal of links might be detectable. Furthermore, the heuristics are most effective when both parties in a relationship coordinate their efforts. Future work may explore "attack-aware" link prediction algorithms designed to counter these strategic rewiring attempts. Nevertheless, these results provide a proactive framework for individuals to safeguard their digital traces in an increasingly connected world.
Summary updated