{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T16:21:55Z","timestamp":1772641315431,"version":"3.50.1"},"reference-count":46,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"8","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC Key Program Project","doi-asserted-by":"publisher","award":["12231002"],"award-info":[{"award-number":["12231002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007937","name":"Elite Undergraduate Training Program of School of Mathematical Science, Peking University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007937","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2023,8]]},"DOI":"10.1109\/tit.2023.3265009","type":"journal-article","created":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T19:07:57Z","timestamp":1681153677000},"page":"5289-5298","source":"Crossref","is-referenced-by-count":18,"title":["Detection Threshold for Correlated Erd\u0151s-R\u00e9nyi Graphs via Densest Subgraph"],"prefix":"10.1109","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3078-3793","authenticated-orcid":false,"given":"Jian","family":"Ding","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3716-7627","authenticated-orcid":false,"given":"Hang","family":"Du","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Peking University, Beijing, China"}]}],"member":"263","reference":[{"key":"ref13","article-title":"Matching recovery threshold for correlated random graphs","author":"ding","year":"2022","journal-title":"arXiv 2205 14650"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3341617.3326151"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"ref15","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"erd?s","year":"1960","journal-title":"Magyar Tud Akad Mat Kutató Int Közl"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010306"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-020-00997-4"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"ref30","article-title":"Testing network correlation efficiently via counting trees","author":"mao","year":"2021","journal-title":"arXiv 2110 11816"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/3410048.3410106","article-title":"Partial recovery of Erd?s-Rényi graph alignment via k-core alignment","author":"cullina","year":"2020","journal-title":"Proc SIGMETRICS"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.33"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901460"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20934"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09444-0_1"},{"key":"ref1","year":"2005","journal-title":"Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing  - HLT '05"},{"key":"ref17","first-page":"2985","article-title":"Spectral graph matching and regularized quadratic relaxations: Algorithm and theory","volume":"119","author":"fan","year":"2020","journal-title":"Proc 37th Int Conf Mach Learn"},{"key":"ref39","first-page":"1","article-title":"Correlated stochastic block models: Exact graph matching with applications to recovering communities","author":"racz","year":"2021","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref16","article-title":"Spectral graph matching and regularized quadratic relaxations II: Erd?s-Rényi graphs and universality","author":"fan","year":"2019","journal-title":"arXiv 1907 08883"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1214\/21-AAP1703"},{"key":"ref19","first-page":"459","article-title":"The k-orientability thresholds for Gn,p","author":"fernholz","year":"2007","journal-title":"Proc 18th Annu ACM-SIAM Symp Discrete Algorithms"},{"key":"ref18","article-title":"Spectral alignment of graphs","author":"feizi","year":"2016","journal-title":"arXiv 1602 04181"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806705"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"ref23","first-page":"2080","article-title":"Impossibility of partial recovery in the graph alignment problem","volume":"134","author":"ganassali","year":"2021","journal-title":"Proc 34th Conf Learn Theory"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1214\/22-AAP1786"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2355"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/18.59935"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000334"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0121002"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"ref22","first-page":"1633","article-title":"From tree matching to sparse graph alignment","volume":"125","author":"ganassali","year":"2020","journal-title":"Proc 33rd Conf Learn Theory"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9518266"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316339831"},{"key":"ref43","first-page":"3441","article-title":"Random graph matching in geometric models: The case of complete graphs","volume":"178","author":"wang","year":"2022","journal-title":"Proc 35th Conf Learn Theory"},{"key":"ref28","first-page":"3513","article-title":"Seeded graph matching for correlated Erdös-Rényi graphs","volume":"15","author":"lyzinski","year":"2014","journal-title":"J Mach Learn Res"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794371"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-022-01184-3"},{"key":"ref8","first-page":"1","article-title":"Balanced graph matching","volume":"19","author":"cour","year":"2006","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref7","first-page":"469","article-title":"The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation","author":"cain","year":"2007","journal-title":"Proc 18th Annu ACM-SIAM Symp Discrete Algorithms"},{"key":"ref9","article-title":"Exact alignment recovery for correlated Erd?s-Rényi graphs","author":"cullina","year":"2017","journal-title":"arXiv 1711 06783"},{"key":"ref4","first-page":"1","article-title":"(Nearly) efficient algorithms for the graph matching problem on correlated random graphs","volume":"32","author":"barak","year":"2019","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1091"},{"key":"ref6","article-title":"Seedless graph matching via tail of degree distribution for correlated Erdös-Rényi graphs","author":"bozorg","year":"2019","journal-title":"arXiv 1907 06334"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.320"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2017.8335178"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/10183383\/10098628.pdf?arnumber=10098628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,7]],"date-time":"2023-08-07T17:58:29Z","timestamp":1691431109000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10098628\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":46,"journal-issue":{"issue":"8"},"URL":"https:\/\/doi.org\/10.1109\/tit.2023.3265009","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8]]}}}