  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.
