De-anonymizing the Partial Web: How Social Networks Leak Privacy via Seeds

TL;DR

Social network de-anonymization is often treated as a graph matching puzzle. This paper reveals that even if an attacker only has a partial view of two different social platforms (partial overlap), they can reveal the identities of almost all users using just a small "seed" of known identities. By extending Bootstrap Percolation theory to the Erdős-Rényi (ER) model, the authors pinpoint the exact "tipping point" where a few known users lead to a total privacy collapse.

Background: The Seeded Attack Logic

Imagine you have an anonymous dataset of Facebook connections and a public dataset of Twitter followers. Even if names are removed, the "shape" of your social circle is unique. Attackers use "seeds"—users whose identities are known on both platforms—to start a chain reaction of identification.

The authors identify a major gap in previous research: most models assume the two networks have the exact same users. In the real world, you might be on Twitter but not Facebook. This paper asks: How much overlap is enough for an attacker to succeed?

The Problem & Motivation: Beyond Perfect Overlap

Prior SOTA work (like Yartseva et al.) established that there is a critical seed size $a_c$. If you have more than $a_c$ seeds, identification spreads like a virus (percolation); if fewer, the attack fails. However, these models break down when the networks only partially overlap.

The authors' insight was to treat the two networks ($G_1$ and $G_2$) as subgraphs of a hidden "master" social network $G$, sampled with specific probabilities for nodes ($h$) and edges ($s$).

Methodology: The Mechanics of Percolation

The core of the attack is the Percolation Graph Matching (PGM) algorithm.

The Logic of "Marks"

1. Start with a seed set of known pairs.
2. For every known pair, look at their neighbors. If a pair of nodes $(i,j)$ are neighbors of many already-matched pairs, they are likely the same person.
3. Once a pair gets $r$ "marks" (evidence), they are considered "infected" (matched), and the process repeats.

The authors mathematically proved that even with partial overlap ($h<1$), the probability of a correct pair getting a mark is significantly higher ($1/p$ factor) than a wrong pair. This gap allows the algorithm to remain accurate even when the data is incomplete.

The "Tipping Point" (Phase Transition)

The most striking contribution is the redefined critical threshold $a_c$: $a_c\approx \left(1-\frac{1}{r}\right){\left(\frac{(r-1)!}{n{q}^r}\right)}^{1/(r-1)}$ Where $q$ incorporates the overlap factor $h^2$. This formula allows us to predict the exact number of seeds an attacker needs based on network density and overlap.

Experimental Validation

The authors tested this on synthetic graphs of 10,000 nodes.

• Synthetic Results: When overlap ($h$) and edge density ($s$) were high, they observed a sharp "Phase Transition." Suddenly, at a specific seed count, the matching accuracy jumps from near-zero to near-total.
• Real-World Data: Testing on academic co-author networks showed that real social networks are often too sparse for this specific chain reaction to occur easily.

The table above shows that the experimental "explosion" of identification happens very close to the predicted mathematical threshold.

Critical Analysis & Takeaways

Why does this matter? It proves that privacy is not a linear problem. You aren't "slightly more at risk" as more data leaks; you are safe until you hit a threshold, after which everyone is deanonymized instantly.

Limitations:

1. The ER Model: Real-world networks aren't Erdős-Rényi; they have "hubs" (popular people) and "communities." The ER model assumes everyone has roughly the same number of friends, which is rarely true.
2. Sparsity: As seen in the real-data experiment, if the network isn't dense enough, the chain reaction dies out.

Final Thought: This work provides a rigorous mathematical foundation for cross-platform privacy. While sparsity protects us today, as social platforms become more integrated and data more dense, we move closer to the critical $a_c$ threshold where anonymity vanishes.