Network Structure and Privacy: The Re-Identification Risk in Graph Data
summary
Finds that neighborhood structure alone re-identifies nodes: authors build uniqueness maps to visualize how many nodes have structurally unique neighborhoods, test Erdos–Renyi and random geometry graphs plus 30 real networks, and show uniqueness rises sharply with average degree (dangerous above ~10–20). Implements uniform edge sampling to lower average degree and estimate/correct structural measures, but shows it is not bulletproof and that multilayer aggregation can increase uniqueness.
AI-written summary · about
chapters (7)
- 0:00Graph data privacy risks
- 1:13Re-identification via graph structure
- 3:03Uniqueness in random graphs
- 5:52Real data risk estimation
- 6:36Mitigating neighborhood uniqueness
- 8:02Key takeaways
- 9:08Multi-layer network analysis
related talks
54mNode Privacy, High-dimensional Graph Summaries, and Block Models
43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust
55mDistribution-Free Models of Social and Information Networks
06mModelling Memory for Individual Re-identification in Decentralised Mobile Contact Tracing ...
01h 43mPerspective
32mThe Dangerous Data Anonymization - Keynote
35mPairwise Network Differential Privacy
29mApplying Randomized Methods for Zonotope Enumeration and...