# An efficient reconciliation algorithm for social networks

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2013.

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

- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [The Power of D-hops in Matching Power-Law Graphs](https://mlsanity.com/paper/2102.12975/) (2021)
- [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)
- [Alignment and Comparison of Directed Networks via Transition Couplings of Random Walks](https://mlsanity.com/paper/2106.07106/) (2021)
- [Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation](https://mlsanity.com/paper/2305.19666/) (2023)
- [Statistical Limits for Testing Correlation of Hypergraphs](https://mlsanity.com/paper/2202.05888/) (2022)
- [Network Alignment](https://mlsanity.com/paper/2504.11367/) (2025)
- [Graph Alignment via Dual-Pass Spectral Encoding and Latent Space Communication](https://mlsanity.com/paper/2509.09597/) (2025)
- [Sharp Statistical Thresholds for Attributed Gaussian Graph Matching](https://mlsanity.com/paper/2603.23305/) (2026)

## Abstract (arXiv)

People today typically use multiple online social networks (Facebook, Twitter, Google+, LinkedIn, etc.). Each online network represents a subset of their "real" ego-networks. An interesting and challenging problem is to reconcile these online networks, that is, to identify all the accounts belonging to the same individual. Besides providing a richer understanding of social dynamics, the problem has a number of practical applications. At first sight, this problem appears algorithmically challenging. Fortunately, a small fraction of individuals explicitly link their accounts across multiple networks; our work leverages these connections to identify a very large fraction of the network. Our main contributions are to mathematically formalize the problem for the first time, and to design a simple, local, and efficient parallel algorithm to solve it. We are able to prove strong theoretical guarantees on the algorithm's performance on well-established network models (Random Graphs, Preferential Attachment). We also experimentally confirm the effectiveness of the algorithm on synthetic and real social network data sets.