AnonSN: Preserving Social Graph Utility Through Intelligent Fake Node Injection

TL;DR

Social network data is a goldmine for researchers, but publishing it safely is a nightmare. Typical anonymization often ruins the "utility" of the data—making the graph look nothing like the original. This paper introduces an enhanced approach that uses fake nodes instead of just adding edges to reach k-anonymity, successfully keeping the Average Path Length (APL) intact for more accurate post-anonymization analysis.

The Structural Privacy Crisis

In social network analysis, your "identity" isn't just your name; it's your neighborhood. Even if your name is removed (naïve anonymization), if an attacker knows you have three friends who are all connected to each other, they can find your unique "structural fingerprint" in a public dataset.

Existing solutions try to fix this by adding edges until every node looks like at least k others. However, connecting two distant nodes to satisfy a local anonymity requirement has a catastrophic global side effect: it creates "wormholes" in the graph, drastically shortening the distance between communities and making the Average Path Length (APL)—a vital metric for information flow—meaningless.

Methodology: High-Fidelity Anonymization

The authors propose a multi-faceted cost function to decide how to mask a node. The standout feature is the intelligent node selection process.

1. The Cost-Based Grouping

The algorithm groups nodes with similar neighborhood structures (represented via adjacency matrices) and calculates an "Anonymization Cost": $Cost(u,v)=\alpha \cdot NCP+\beta \cdot (n{b}_{edges})+\gamma \cdot (n{b}_{existing\_nodes})+\delta \cdot (n{b}_{fake\_nodes})$ By tuning these weights, the system can prioritize adding nodes over edges if it preserves structural utility.

2. Smart Node Injection

Instead of blindly adding a node, the algorithm runs a check:

• It first calculates the original average distance of the target node using Dijkstra's algorithm.
• It then simulates adding an existing unanonymized node or a brand-new "fake" node.
• It picks the option that keeps the new average distance closest to the original value.

Figure 1: The overall workflow of the AnonSN approach, highlighting the neighborhood extraction and matching phase.

Experimental Validation

The authors tested their approach against the benchmark Zhou & Pei algorithm across various datasets.

Key Findings:

• APL Stability: While the baseline algorithm saw APL crash as k (the anonymity level) increased, the "AnonSN" method remained remarkably stable.
• Lower Distortion: In the Krackfr_271 graph test, the distortion in APL was significantly lower—nearly 5% better at $k=10$.
• Versatility: The method proved effective on both real-world email/social data and synthetic power-law graphs.

Figure 2: Performance comparison showing that as k increases, the baseline APL (Zhou and Pei) deviates significantly, whereas AnonSN tracks the original graph closer.

Critical Insight: Why Nodes Beat Edges

The physical intuition here is simple: adding an edge is a global change. It links two previously separate parts of the graph, potentially creating a shortcut for every other node. Adding a node (specifically a "pendant" or leaf node) is a local change. It helps satisfy the "number of neighbors" requirement for one node without fundamentally altering the shortest paths between everyone else in the network.

Conclusion & Future Directions

The "AnonSN" algorithm proves that we don't have to sacrifice graph utility for privacy. By shifting the focus from "edge rewiring" to "node injection," researchers can still perform meaningful distance-based analysis on anonymized data.

However, there is a catch: the cost of storage. Adding fake nodes increases the graph size. The next frontier for this research lies in balancing the "number of fake nodes" against the "quality of utility" to ensure the datasets don't become too bloated for practical compute environments.