Deanonymizing Mobility Traces: The Social Network as a Dangerous Side-Channel
Deanonymizing Mobility Traces: Using Social Networks as a Side-Channel
This paper presents a deanonymization framework that leverages social network graphs as a side-channel to identify users in anonymized mobility traces. By correlating a structural "contact graph" derived from mobility data with a known social network, the authors achieve over 80% identification accuracy across three real-world datasets (St Andrews, Smallblue, and Infocom06).
TL;DR
Can your social life betray your location privacy? This research proves that even if a mobility trace is "anonymized" by removing names and IDs, the patterns of who you meet—mirrored in your social networks like Facebook or LinkedIn—can be used to re-identify you with 80%+ accuracy. By treating meetings as edges in a Contact Graph, researchers can "map" them back to a Social Network, effectively unmasking anonymous users.
The Background: Why PII Masking Fails
Location-Based Services (LBS) often collect GPS or Bluetooth traces for traffic forecasting or urban planning. To "protect" us, they strip away names and addresses.
However, this paper highlights a critical oversight: We are defined by our connections. If User A meets User B frequently, and in the real-world Social Network, Alice and Bob are friends, that structural link is a fingerprint. The authors posit that as long as we have access to a social graph (which is often public or semi-public), anonymized mobility data is a sitting duck.
The Insight: From Traces to Graphs
The authors bridge the gap between "location points" and "social links" by constructing a Contact Graph.
- Contact Graph (): Nodes are anonymous users. An edge exists if two users were in the same place at the same time.
- Social Network (): Nodes are known identities. Edges represent real-world relationships (friends, co-authors).
The challenge is a Graph Alignment problem: How do we find a mapping between and when the graphs aren't identical and the search space is astronomically large?
Methodology: The Three-Step Attack
1. Bootstrapping with Landmark Nodes
Since a brute-force match of every node is impossible ( complexity), the authors first find "Landmarks"—the celebrities or popular hubs of the network. They use a novel Centrality Measure based on opportunistic paths to identify these key users in both graphs.
2. Recursive Sub-Graph Matching (The Winning Strategy)
The most effective method proposed was Recursive Sub-Graph Matching. It treats deanonymization as a Constraint Satisfaction Problem (CSP). Starting from the landmarks, it asks: "If I know Bob is User_1, and User_2 meets User_1, who in Bob’s social circle is most likely to be User_2?"
3. Handling the "Noise"
Real-world data is messy. Social networks are incomplete, and mobility data is often obfuscated. The researchers tested their system against:
- Edge Noise: Deleting or adding friendships.
- Spurious Nodes: Adding people to the social network who aren't in the mobility trace.
- Location Obfuscation: Adding random GPS noise.
Surprisingly, the system was highly resilient. Even with 25% noise, accuracy remained high, especially when using advanced filters like Kalman Filtering to clean the mobility data before matching.
Experimental Results: High Fidelity Unmasking
The researchers tested three distinct environments:
- St Andrews: WiFi-based campus traces.
- Smallblue: Internal enterprise IM chats.
- Infocom06: Bluetooth contacts at a tech conference.
The Recursive Sub-Graph (SG) method reached nearly 90% accuracy in some scenarios. It approached the "Automorphism Bound"—the theoretical limit of how much information can be extracted from a graph's structure.
Critical Analysis & Conclusion
The core contribution of this work is the realization that privacy is not an individual attribute; it is a relational one.
Takeaways:
- Centrality is a vulnerability: If you are a high-centrality "hub" in your social circle, you are easier to deanonymize.
- Obfuscation must be structural: To truly protect mobility traces, we must break the structural similarity between contact patterns and social graphs, not just add noise to GPS coordinates.
Limitations: The study uses relatively small datasets (up to 125 nodes). As we scale to cities with millions of users, the computational cost of CSP increases, and the "uniqueness" of sub-graphs might shift, potentially making landmarks harder to distinguish among millions of peers.
Future Work: This research paves the way for "Relational Privacy" where we protect not just where you are, but who you are with.