{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T15:14:55Z","timestamp":1784646895858,"version":"3.55.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 16-17286"],"award-info":[{"award-number":["CCF 16-17286"]}],"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,12,17]]},"abstract":"<jats:p>We determine information theoretic conditions under which it is possible to partially recover the alignment used to generate a pair of sparse, correlated Erdos-Renyi graphs. To prove our achievability result, we introduce the k-core alignment estimator. This estimator searches for an alignment in which the intersection of the correlated graphs using this alignment has a minimum degree of k. We prove a matching converse bound. As the number of vertices grows, recovery of the alignment for a fraction of the vertices tending to one is possible when the average degree of the intersection of the graph pair tends to infinity. It was previously known that exact alignment is possible when this average degree grows faster than the logarithm of the number of vertices.<\/jats:p>","DOI":"10.1145\/3366702","type":"journal-article","created":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T13:21:11Z","timestamp":1576675271000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Partial Recovery of Erd\u00f0s-R\u00e9nyi Graph Alignment via k-Core Alignment"],"prefix":"10.1145","volume":"3","author":[{"given":"Daniel","family":"Cullina","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Negar","family":"Kiyavash","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prateek","family":"Mittal","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H. Vincent","family":"Poor","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392023"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"e_1_2_1_3_1","volume-title":"Exact alignment recovery for correlated ErdHos R\u00e9nyi graphs","author":"Cullina D.","year":"2017","unstructured":"BIBentryALTinterwordspacing D. Cullina and N. Kiyavash , \u201c Exact alignment recovery for correlated ErdHos R\u00e9nyi graphs ,\u201d arXiv:1711.06783 [cs, math], Nov. 2017 , arXiv: 1711.06783. [Online]. Available: http:\/\/arxiv.org\/abs\/1711.06783BIBentrySTDinterwordspacing BIBentryALTinterwordspacingD. Cullina and N. Kiyavash, \u201cExact alignment recovery for correlated ErdHos R\u00e9nyi graphs,\u201d arXiv:1711.06783 [cs, math], Nov. 2017, arXiv: 1711.06783. [Online]. Available: http:\/\/arxiv.org\/abs\/1711.06783BIBentrySTDinterwordspacing"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901460"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7446983"},{"key":"e_1_2_1_6_1","volume-title":"Typicality Matching for Pairs of Correlated Graphs","author":"Shirani F.","year":"1802","unstructured":"F. Shirani , S. Garg , and E. Erkip , \u201c Typicality Matching for Pairs of Correlated Graphs ,\u201d arXiv preprint arXiv: 1802 .00918, 2018. F. Shirani, S. Garg, and E. Erkip, \u201cTypicality Matching for Pairs of Correlated Graphs,\u201d arXiv preprint arXiv:1802.00918, 2018."},{"key":"e_1_2_1_7_1","volume-title":"Fundamental Limits of Database Alignment","author":"Cullina D.","year":"1805","unstructured":"BIBentryALTinterwordspacing D. Cullina , P. Mittal , and N. Kiyavash , \u201c Fundamental Limits of Database Alignment ,\u201d arXiv: 1805 .03829 [cs, math], May 2018, arXiv: 1805.03829. [Online]. Available: http:\/\/arxiv.org\/abs\/1805.03829BIBentrySTDinterwordspacing BIBentryALTinterwordspacingD. Cullina, P. Mittal, and N. Kiyavash, \u201cFundamental Limits of Database Alignment,\u201d arXiv:1805.03829 [cs, math], May 2018, arXiv: 1805.03829. [Online]. Available: http:\/\/arxiv.org\/abs\/1805.03829BIBentrySTDinterwordspacing"},{"key":"e_1_2_1_8_1","volume-title":"On Your Social Network De-anonymizablity: Quantification and Large Scale Evaluation with Seed Knowledge","author":"Ji S.","year":"2015","unstructured":"S. Ji , W. Li , N. Z. Gong , P. Mittal , and R. Beyah , \u201c On Your Social Network De-anonymizablity: Quantification and Large Scale Evaluation with Seed Knowledge ,\u201d 2015 . S. Ji, W. Li, N. Z. Gong, P. Mittal, and R. Beyah, \u201cOn Your Social Network De-anonymizablity: Quantification and Large Scale Evaluation with Seed Knowledge,\u201d 2015."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139550.3139562"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732274"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv130"},{"key":"e_1_2_1_13_1","first-page":"f20100063","article-title":"Topological network alignment uncovers biological function and phylogeny","author":"Kuchaiev O.","year":"2010","unstructured":"O. Kuchaiev , T. Milenkovic , V. Memievic , W. Hayes , and N. Prulj , \u201c Topological network alignment uncovers biological function and phylogeny ,\u201d Journal of the Royal Society Interface , p. rsi f20100063 , 2010 . O. Kuchaiev, T. Milenkovic, V. Memievic, W. Hayes, and N. Prulj, \u201cTopological network alignment uncovers biological function and phylogeny,\u201d Journal of the Royal Society Interface, p. rsif20100063, 2010.","journal-title":"Journal of the Royal Society Interface"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"issue":"1","key":"e_1_2_1_16_1","first-page":"2","article-title":"SAPPER: subgraph indexing and approximate matching in large graphs","volume":"3","author":"Zhang S.","year":"2010","unstructured":"S. Zhang , J. Yang , and W. Jin , \u201c SAPPER: subgraph indexing and approximate matching in large graphs ,\u201d Proceedings of the VLDB Endowment , vol. 3 , no. 1 -- 2 , pp. 1185--1194, 2010 . S. Zhang, J. Yang, and W. Jin, \u201cSAPPER: subgraph indexing and approximate matching in large graphs,\u201d Proceedings of the VLDB Endowment, vol. 3, no. 1--2, pp. 1185--1194, 2010.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794371"},{"key":"e_1_2_1_19_1","first-page":"1598","volume-title":"2013 51st Annual Allerton Conference on. hskip 1em plus 0.5em minus 0.4emrelax IEEE","author":"Pedarsani P.","year":"2013","unstructured":"P. Pedarsani , D. R. Figueiredo , and M. Grossglauser , \u201c A bayesian method for matching two similar graphs without seeds,\u201d in Communication, Control, and Computing (Allerton) , 2013 51st Annual Allerton Conference on. hskip 1em plus 0.5em minus 0.4emrelax IEEE , 2013 , pp. 1598 -- 1607 . P. Pedarsani, D. R. Figueiredo, and M. Grossglauser, \u201cA bayesian method for matching two similar graphs without seeds,\u201d in Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on. hskip 1em plus 0.5em minus 0.4emrelax IEEE, 2013, pp. 1598--1607."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2750357"},{"key":"e_1_2_1_21_1","volume-title":"Spectral Alignment of Graphs","author":"Feizi S.","year":"2016","unstructured":"BIBentryALTinterwordspacing S. Feizi , G. Quon , M. Recamonde-Mendoza , M. Medard , M. Kellis , and A. Jadbabaie , \u201c Spectral Alignment of Graphs ,\u201d arXiv:1602.04181 [cs, math], Feb. 2016 , arXiv: 1602.04181. [Online]. Available: http:\/\/arxiv.org\/abs\/1602.04181BIBentrySTDinterwordspacing BIBentryALTinterwordspacingS. Feizi, G. Quon, M. Recamonde-Mendoza, M. Medard, M. Kellis, and A. Jadbabaie, \u201cSpectral Alignment of Graphs,\u201d arXiv:1602.04181 [cs, math], Feb. 2016, arXiv: 1602.04181. [Online]. Available: http:\/\/arxiv.org\/abs\/1602.04181BIBentrySTDinterwordspacing"},{"issue":"1","key":"e_1_2_1_22_1","first-page":"1","article-title":"Graph matching: Relax at your own risk","author":"Lyzinski V.","year":"2016","unstructured":"V. Lyzinski , D. Fishkind , M. Fiori , J. Vogelstein , C. Priebe , and G. Sapiro , \u201c Graph matching: Relax at your own risk ,\u201d IEEE Transactions on Pattern Analysis & Machine Intelligence , no. 1 , pp. 1 -- 1 , 2016 . V. Lyzinski, D. Fishkind, M. Fiori, J. Vogelstein, C. Priebe, and G. Sapiro, \u201cGraph matching: Relax at your own risk,\u201d IEEE Transactions on Pattern Analysis & Machine Intelligence, no. 1, pp. 1--1, 2016.","journal-title":"IEEE Transactions on Pattern Analysis & Machine Intelligence"},{"key":"e_1_2_1_23_1","volume-title":"(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs","author":"Barak B.","year":"1805","unstructured":"B. Barak , C.-N. Chou , Z. Lei , T. Schramm , and Y. Sheng , \u201c (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs ,\u201d arXiv preprint arXiv: 1805 .02349, 2018. B. Barak, C.-N. Chou, Z. Lei, T. Schramm, and Y. Sheng, \u201c(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs,\u201d arXiv preprint arXiv:1805.02349, 2018."},{"key":"e_1_2_1_24_1","volume-title":"Seeded Graph Matching via Large Neighborhood Statistics","author":"Mossel E.","year":"1807","unstructured":"E. Mossel and J. Xu , \u201c Seeded Graph Matching via Large Neighborhood Statistics ,\u201d arXiv preprint arXiv: 1807 .10262, 2018. E. Mossel and J. Xu, \u201cSeeded Graph Matching via Large Neighborhood Statistics,\u201d arXiv preprint arXiv:1807.10262, 2018."},{"key":"e_1_2_1_25_1","volume-title":"BIBforeignlanguageenThe Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness","author":"Moore C.","year":"2017","unstructured":"BIBentryALTinterwordspacing C. Moore , \u201c BIBforeignlanguageenThe Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness ,\u201d Feb. 2017 . [Online]. Available: https:\/\/arxiv.org\/abs\/1702.00467BIBentrySTDinterwordspacing BIBentryALTinterwordspacingC. Moore, \u201cBIBforeignlanguageenThe Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness ,\u201d Feb. 2017. [Online]. Available: https:\/\/arxiv.org\/abs\/1702.00467BIBentrySTDinterwordspacing"},{"key":"e_1_2_1_26_1","volume-title":"Community detection and stochastic block models: recent developments","author":"Abbe E.","year":"2017","unstructured":"BIBentryALTinterwordspacing E. Abbe , \u201c Community detection and stochastic block models: recent developments ,\u201d arXiv:1703.10146 [cs, math, stat], Mar. 2017 , arXiv: 1703.10146. [Online]. Available: http:\/\/arxiv.org\/abs\/1703.10146BIBentrySTDinterwordspacing BIBentryALTinterwordspacingE. Abbe, \u201cCommunity detection and stochastic block models: recent developments,\u201d arXiv:1703.10146 [cs, math, stat], Mar. 2017, arXiv: 1703.10146. [Online]. Available: http:\/\/arxiv.org\/abs\/1703.10146BIBentrySTDinterwordspacing"},{"key":"e_1_2_1_27_1","volume-title":"Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits","author":"Wu Y.","year":"1806","unstructured":"BIBentryALTinterwordspacing Y. Wu and J. Xu , \u201c Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits ,\u201d arXiv: 1806 .00118 [cs, math, stat], May 2018, arXiv: 1806.00118. [Online]. Available: http:\/\/arxiv.org\/abs\/1806.00118BIBentrySTDinterwordspacing BIBentryALTinterwordspacingY. Wu and J. Xu, \u201cStatistical Problems with Planted Structures: Information-Theoretical and Computational Limits,\u201d arXiv:1806.00118 [cs, math, stat], May 2018, arXiv: 1806.00118. [Online]. Available: http:\/\/arxiv.org\/abs\/1806.00118BIBentrySTDinterwordspacing"},{"key":"e_1_2_1_28_1","volume-title":"The evolution of sparse graphs","author":"Bollob\u00e1s B.","year":"1983","unstructured":"B. Bollob\u00e1s , The evolution of sparse graphs , Graph Theory and Combinatorics (Cambridge 1983 ), 35--57. hskip 1em plus 0.5em minus 0.4emrelax Academic Press , London, 1984. B. Bollob\u00e1s, The evolution of sparse graphs, Graph Theory and Combinatorics (Cambridge 1983), 35--57. hskip 1em plus 0.5em minus 0.4emrelax Academic Press, London, 1984."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90162-U"}],"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\/3366702","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366702","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:39Z","timestamp":1750203879000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,17]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,12,17]]}},"alternative-id":["10.1145\/3366702"],"URL":"https:\/\/doi.org\/10.1145\/3366702","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,17]]},"assertion":[{"value":"2019-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}