{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T16:21:51Z","timestamp":1772641311337,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T00:00:00Z","timestamp":1560902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014036","name":"Multidisciplinary University Research Initiative","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100014036","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,6,19]]},"abstract":"<jats:p>\n            Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erd\u00f6s-R\u00e9nyi graphs. However, very little is known about the existence of efficient algorithms to achieve graph alignment without seeds. In this work we identify a region in which a straightforward O(n\n            <jats:sup>11\/5<\/jats:sup>\n            log n)-time canonical labeling algorithm, initially introduced in the context of graph isomorphism, succeeds in aligning correlated Erdos-R\u00e9nyi graphs. The algorithm has two steps. In the first step, all vertices are labeled by their degrees and a trivial minimum distance alignment (i.e., sorting vertices according to their degrees) matches a fixed number of highest degree vertices in the two graphs. Having identified this subset of vertices, the remaining vertices are matched using a alignment algorithm for bipartite graphs. Finally, we show that the implementation of a variant of this algorithm allows for the efficient alignment of large graphs under limited noise.\n          <\/jats:p>","DOI":"10.1145\/3341617.3326151","type":"journal-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:18:56Z","timestamp":1561033136000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdos-R\u00e9nyi Graphs"],"prefix":"10.1145","volume":"3","author":[{"given":"Osman Emre","family":"Dai","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Cullina","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Negar","family":"Kiyavash","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Grossglauser","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920988"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2017.8262775"},{"key":"e_1_2_1_4_1","first-page":"709","volume-title":"Systems and Computers","author":"Onaran E.","year":"2016","unstructured":"E. Onaran, S. Garg, and E. Erkip, \"Optimal de-anonymization in random graphs with community structure,\" in 2016 50th Asilomar Conference on Signals, Systems and Computers, pp. 709--713, IEEE, 2016."},{"key":"e_1_2_1_5_1","volume-title":"De-anonymization of social networks with communities: When quantifications meet algorithms","author":"Fu L.","year":"2017","unstructured":"L. Fu, X. Fu, Z. Hu, Z. Xu, and X. Wang, \"De-anonymization of social networks with communities: When quantifications meet algorithms,\" 2017."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2010.0063"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv130"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu409"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt071"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043199"},{"key":"e_1_2_1_12_1","volume-title":"Internet Society","author":"Ji S.","year":"2015","unstructured":"S. Ji, W. Li, N. Z. Gong, P. Mittal, and R. Beyah, \"On your social network de-anonymizablity: Quantification and large scale evaluation with seed knowledge,\" in Proceedings 2015 Network and Distributed System Security Symposium, Internet Society, 2015."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.33"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732274"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310497"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794371"},{"key":"e_1_2_1_18_1","volume-title":"It's who you know,\" in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD","author":"Henderson K.","year":"2011","unstructured":"K. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Rad, H. Tong, and C. Faloutsos, \"It's who you know,\" in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD 2011, ACM Press, 2011."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2013.6736720"},{"key":"e_1_2_1_20_1","volume-title":"(nearly) efficient algorithms for the graph matching problem on correlated random graphs,\" arXiv preprint arXiv:1805.02349","author":"Barak B.","year":"2018","unstructured":"B. Barak, C.-N. Chou, Z. Lei, T. Schramm, and Y. Sheng, \"(nearly) efficient algorithms for the graph matching problem on correlated random graphs,\" arXiv preprint arXiv:1805.02349, 2018."},{"key":"e_1_2_1_21_1","volume-title":"Reconciling graphs and sets of sets","author":"Mitzenmacher M.","year":"2017","unstructured":"M. Mitzenmacher and T. Morgan, \"Reconciling graphs and sets of sets,\" 2017."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"D. Cullina and N. Kiyavash \"Improved achievability and converse bounds for erdos-renyi graph matching \" in Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science - SIGMETRICS 2016 ACM Press 2016.","DOI":"10.1145\/2896377.2901460"},{"key":"e_1_2_1_24_1","first-page":"06783","article-title":"Exact alignment recovery for correlated erdos renyi graphs","volume":"1711","author":"Cullina D.","year":"2017","unstructured":"D. Cullina and N. Kiyavash, \"Exact alignment recovery for correlated erdos renyi graphs,\" CoRR, vol. abs\/1711.06783, 2017.","journal-title":"CoRR"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_2_1_27_1","volume-title":"Spectral alignment of graphs,\" arXiv preprint arXiv:1602.04181","author":"Feizi S.","year":"2016","unstructured":"S. Feizi, G. Quon, M. Recamonde-Mendoza, M. Medard, M. Kellis, and A. Jadbabaie, \"Spectral alignment of graphs,\" arXiv preprint arXiv:1602.04181, 2016."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326151","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341617.3326151","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341617.3326151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:29Z","timestamp":1750200089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,19]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,19]]}},"alternative-id":["10.1145\/3341617.3326151"],"URL":"https:\/\/doi.org\/10.1145\/3341617.3326151","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,19]]},"assertion":[{"value":"2019-06-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}