# Optimal De-Anonymization in Random Graphs with Community Structure

arXiv: https://arxiv.org/abs/1602.01409 · HTML: https://mlsanity.com/paper/1602.01409/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2016.

## Built on by (most cited first, 11 of 11)

- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator](https://mlsanity.com/paper/2302.05407/) (2023)
- [SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching](https://mlsanity.com/paper/2205.13679/) (2022)
- [Clustered Graph Matching for Label Recovery and Graph Classification](https://mlsanity.com/paper/2205.03486/) (2022)
- [Shuffled linear regression through graduated convex relaxation](https://mlsanity.com/paper/2209.15608/) (2022)
- [Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation](https://mlsanity.com/paper/2305.19666/) (2023)
- [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Covariate-assisted graph matching](https://mlsanity.com/paper/2512.11761/) (2025)

## Abstract (arXiv)

Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, we (i) characterize the maximum a posteriori (MAP) estimates of user identities for the anonymized graph and (ii) provide sufficient conditions for successful de-anonymization for underlying graphs with community structure. Our results generalize prior work that assumed underlying graphs of ErdHos-R'enyi type, in addition to proving the optimality of the attack strategy adopted in the prior work.