{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T18:40:56Z","timestamp":1791225656370,"version":"4.1.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.14778\/2732269.2732274","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"377-388","source":"Crossref","is-referenced-by-count":182,"title":["An efficient reconciliation algorithm for social networks"],"prefix":"10.14778","volume":"7","author":[{"given":"Nitish","family":"Korula","sequence":"first","affiliation":[{"name":"Google Inc., New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google Inc., New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Dblp. http:\/\/dblp.uni-trier.de\/xml\/.  Dblp. http:\/\/dblp.uni-trier.de\/xml\/."},{"key":"e_1_2_1_2_1","unstructured":"Wikipedia dumps. http:\/\/dumps.wikimedia.org\/.  Wikipedia dumps. http:\/\/dumps.wikimedia.org\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13470-8_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0002-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.007"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1568639"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"Erd\u0151s P.","year":"1959","unstructured":"P. Erd\u0151s and A. R\u00e9nyi . On Random Graphs I. Publ. Math. Debrecen , 6 : 290 -- 297 , 1959 . P. Erd\u0151s and A. R\u00e9nyi. On Random Graphs I. Publ. Math. Debrecen, 6: 290--297, 1959.","journal-title":"On Random Graphs I. Publ. Math. Debrecen"},{"key":"e_1_2_1_12_1","first-page":"211","volume-title":"Marketing Letters","author":"Goldenberg J.","year":"2001","unstructured":"J. Goldenberg , B. Libai , and E. Muller . Talk of the network: Complex systems look at the underlying process of word-of-mouth . Marketing Letters 2001 , pages 211 -- 223 . J. Goldenberg, B. Libai, and E. Muller. Talk of the network: Complex systems look at the underlying process of word-of-mouth. Marketing Letters 2001, pages 211--223."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/202051"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020512"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_2_1_16_1","volume-title":"CEAS conference","author":"Klimmt B.","year":"2004","unstructured":"B. Klimmt and Y. Yang . Introducing the enron corpus . In CEAS conference 2004 . B. Klimmt and Y. Yang. Introducing the enron corpus. In CEAS conference 2004."},{"key":"e_1_2_1_17_1","first-page":"51","volume-title":"ACM Social Network Mining and Analysis","author":"Labitzke S.","year":"2011","unstructured":"S. Labitzke , I. Taranu , and H. Hartenstein . What your friends tell others about you: Low cost linkability of social network profiles . In ACM Social Network Mining and Analysis 2011 , pages 51 -- 60 . S. Labitzke, I. Taranu, and H. Hartenstein. What your friends tell others about you: Low cost linkability of social network profiles. In ACM Social Network Mining and Analysis 2011, pages 51--60."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536474"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.184"},{"key":"e_1_2_1_21_1","volume-title":"Comparison Methods for Stochastic Models and Risks","author":"M\u0171ller A.","year":"2002","unstructured":"A. M\u0171ller and D. Stoyan . Comparison Methods for Stochastic Models and Risks . Wiley , 2002 . A. M\u0171ller and D. Stoyan. Comparison Methods for Stochastic Models and Risks. Wiley, 2002."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718519"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988678"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2245276.2245413"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"e_1_2_1_27_1","first-page":"85","volume-title":"USENIX","author":"Rao J. R.","year":"2000","unstructured":"J. R. Rao and P. Rohatgi . Can pseudonymity really guarantee privacy ? In USENIX 2000 , pages 85 -- 96 . J. R. Rao and P. Rohatgi. Can pseudonymity really guarantee privacy? In USENIX 2000, pages 85--96."},{"key":"e_1_2_1_28_1","volume-title":"Web Science Conference","author":"Rowe M.","year":"2010","unstructured":"M. Rowe and F. Ciravegna . Harnessing the social web: The science of identity disambiguation . In Web Science Conference 2010 . M. Rowe and F. Ciravegna. Harnessing the social web: The science of identity disambiguation. In Web Science Conference 2010."},{"key":"e_1_2_1_29_1","first-page":"1123","volume-title":"WWW","author":"Schoenebeck G.","year":"2013","unstructured":"G. Schoenebeck . Potential networks, contagious communities, and understanding social network structure . In WWW 2013 , pages 1123 -- 1132 . G. Schoenebeck. Potential networks, contagious communities, and understanding social network structure. In WWW 2013, pages 1123--1132."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.923723"},{"key":"e_1_2_1_33_1","first-page":"354","volume-title":"ICWSM","author":"Zafarani R.","year":"2009","unstructured":"R. Zafarani and H. Liu . Connecting corresponding identities across communities . In ICWSM 2009 , pages 354 -- 357 . R. Zafarani and H. Liu. Connecting corresponding identities across communities. In ICWSM 2009, pages 354--357."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732269.2732274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:27:44Z","timestamp":1672223264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732269.2732274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.14778\/2732269.2732274"],"URL":"https:\/\/doi.org\/10.14778\/2732269.2732274","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}