{"entities":{"Q6183756":{"pageid":13318644,"ns":120,"title":"Item:Q6183756","lastrevid":58747809,"modified":"2026-04-06T14:06:25Z","type":"item","id":"Q6183756","labels":{"en":{"language":"en","value":"Matching recovery threshold for correlated random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7783516"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$268F39FC-EB9A-4092-9AB9-391174CC15E3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"44c3e0a54d1c995702041a62fda4762eb31d54c4","datavalue":{"value":{"text":"Matching recovery threshold for correlated random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6183756$C4EA492F-0457-4A8D-8683-BAB36B25BA3B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0b73f6da78562727d9e1c290db85e0053cdeb667","datavalue":{"value":{"entity-type":"item","numeric-id":60819,"id":"Q60819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$E6E38CA7-1F8A-4E65-A46F-DB02C3F98A6B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dbcbfb6e4245007aaaf5b11e066d304c97507b7a","datavalue":{"value":{"time":"+2024-01-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6183756$BEA5DD55-C0B0-4A8D-BDBB-04171D6E718B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41090aa646a2654d7ac934ffb85c9d920e5d747a","datavalue":{"value":"https://arxiv.org/abs/2205.14650","type":"string"},"datatype":"url"},"type":"statement","id":"Q6183756$B090A0DA-0E12-472B-A5E3-9CB5EECDBCEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a0d2089a43e30d11801fe8f0b44eb645e7586cbd","datavalue":{"value":"https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-4/Matching-recovery-threshold-for-correlated-random-graphs/10.1214/23-AOS2305.full","type":"string"},"datatype":"url"},"type":"statement","id":"Q6183756$492CE329-603C-4424-B521-08322134A28A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97d216f30a200254bad7921e7672f29d0d9532db","datavalue":{"value":"This paper studies a recovery-type problem for correlated (coupled) random graphs that are obtained as random subgraphs of the same Erd\u0151s-R\u00e9nyi graph. More precisely, first we take an Erd\u0151s-R\u00e9nyi graph \\(G=(V, E)\\) on \\(n\\) (labeled) vertices with edge probabilities \\(p\\). We keep each edge of \\(G\\) independently with probability \\(s\\) to obtain \\(G_1=(V, E_1)\\). Then we apply a randomly chosen permutation \\(\\pi^\\ast: V\\rightarrow V\\) on the vertices of \\(G\\), this generates a labeled graph \\(G^\\ast\\) (two vertices \\(v\\), \\(w\\) in \\(G^\\ast\\) are connected to each other if and only if \\((\\pi^\\ast)^{-1}(v)\\) and \\((\\pi^\\ast)^{-1}(w)\\) are connected to each other in \\(G\\)). Finally, independently of \\(G_1\\) and each other, we keep each edge of \\(G^\\ast\\) with probability \\(s\\) to get \\(G_2=(V_2, E_2)\\). The question is the following: given \\(G_1\\) and \\(G_2\\), how can we find the matching \\(\\hat\\pi\\) for which the overlap \\((\\pi^\\ast, \\hat \\pi)=|\\{v\\in V: \\pi^\\ast(v)=\\hat\\pi(v)\\}|\\) is maximal? That is, given the two independent unlabeled copies of random subgraphs of the same Erd\u0151s-R\u00e9nyi graph \\(G\\), the goal is to find the pairs of vertices that correspond to the same node in the original graph.  The paper provides a sharp information-theoretic threshold for partial recovery, that is, determines \\(\\delta\\) for which \\((\\pi^\\ast, \\hat \\pi)\\geq \\delta n\\) can be achieved for sequences of random graphs with \\(p=p_n=n^{-\\alpha}+o(1)\\). It turns out that the threshold is the same as the threshold for detecting correlation (i.e.\\ testing this correlated version against two completely independent copies of random graphs). The construction of the optimal matching also relies on the methods of \\textit{J. Ding} and \\textit{H. Hu} [IEEE Trans. Inf. Theory 69, No. 8, 5289--5298 (2023; \\url{doi:10.1109/TIT.2023.3265009})]. Still, in order to obtain the precise threshold for partial recovery, the authors give strong bounds on quantities derived from edge orbits. As for the other direction, to show that partial recovery is not possible for large enough \\(\\delta\\), the argument is based on a truncated version of the second-moment method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6183756$D91299CA-BC2D-44CF-8A53-E23453F97F33","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3793bd5e5a26708a005cf613c99d06b41f5f9956","datavalue":{"value":{"entity-type":"item","numeric-id":428527,"id":"Q428527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$8A46C88F-F153-4C4D-9DF8-CA0B20229D99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6183756$F2AC261D-B74E-4B3E-B4A3-C08A2C5ED136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6183756$85BCC924-B71C-46AB-88FE-D5D0364F970A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6183756$98DF0D9C-3567-40C9-A96D-9E257F86B638","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b8a297f3898e442a0263af76cbe6f526ee75651","datavalue":{"value":"7783516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6183756$AA9D8501-4828-4338-8234-1786034EFD9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f243d05cb875dcc66c9d49e19dc6c08a0a2130b5","datavalue":{"value":"correlated Erd\u0151s-R\u00e9nyi random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6183756$B98EF1AE-FBEF-47F5-A008-5184E35F3461","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf4077658c08a71fdfd8a163c7bb4310d01953bf","datavalue":{"value":"matching recovery","type":"string"},"datatype":"string"},"type":"statement","id":"Q6183756$C3DEA5DE-ADE1-4D2B-9F0C-6078D07E78F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16876a90a1080f6a26a8af0681e0bf4585fa6530","datavalue":{"value":"information threshold","type":"string"},"datatype":"string"},"type":"statement","id":"Q6183756$B1C72F8A-F958-4490-80E6-15D98E7173C7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$30E9125D-3A8A-4746-ADB6-6E4639DFE9CE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe3ac3bc3b4417df2dfa8a76e182a4a1b02d36bd","datavalue":{"value":{"entity-type":"item","numeric-id":4450065,"id":"Q4450065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$DB26827C-9B86-47AA-8EA5-3F47001F412B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d68add8247263f8b50fbb95a749dc50e83b2fa5a","datavalue":{"value":{"entity-type":"item","numeric-id":259578,"id":"Q259578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$CF878938-8B28-41B1-8A68-1F2480C4FD29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abb2e6bbf34e701d48f4af68eec85f23910a2bd6","datavalue":{"value":{"entity-type":"item","numeric-id":1201189,"id":"Q1201189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$FFDAF1E3-46EB-4C00-8562-3927BAB9B404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb50c08199140078e704d177e47f50f5e98a8875","datavalue":{"value":{"entity-type":"item","numeric-id":2934628,"id":"Q2934628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$A96CA32D-42D3-414E-8DD0-C30D86CC9F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b5799914a452a79438624693be5233374ca1b5","datavalue":{"value":{"entity-type":"item","numeric-id":2976660,"id":"Q2976660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$0653FA33-ED3C-4D04-8AD3-643E0799AD34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c5c732ed684bd849b7408aed5ba3bdb06441fd","datavalue":{"value":{"entity-type":"item","numeric-id":2660385,"id":"Q2660385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$EC9AF139-8133-4D42-AD32-D339C43468C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fc8dab424bf618cd5ad53a82284f8333bf55c3f","datavalue":{"value":{"entity-type":"item","numeric-id":6095833,"id":"Q6095833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$8D267C21-12C4-4370-91D2-D91EB1F8EEC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9eeae31f9400e34ca0a25c7cbcb1c7b6e23061d9","datavalue":{"value":{"entity-type":"item","numeric-id":6072327,"id":"Q6072327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$BAB24418-2920-4650-93F2-34628742CA0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f53a971edb0848508cdae8cab7d69b463e38b077","datavalue":{"value":{"entity-type":"item","numeric-id":2934627,"id":"Q2934627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$BFAD57FD-8075-45EE-824B-6479F02DDA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2b5486146e4e728f967e11cde72c5ce56a37a5","datavalue":{"value":{"entity-type":"item","numeric-id":5366923,"id":"Q5366923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$A806C748-BE74-4030-A83C-7D40D6B033B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25ae01012e656d0bae282bb10dcbc843637ff552","datavalue":{"value":{"entity-type":"item","numeric-id":2949990,"id":"Q2949990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$DE7C44DD-ACA9-443D-AC81-AFC109124CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3344f66f2f42cc1c106283bb533dceb5416859d9","datavalue":{"value":{"entity-type":"item","numeric-id":2875136,"id":"Q2875136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$35EBEC8E-9201-4DBE-8E65-B32BB8D234E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6d524b5e95bab83f322bb147d1cbcb44d745841","datavalue":{"value":{"entity-type":"item","numeric-id":3204318,"id":"Q3204318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$3C825A44-43CC-4BD4-AEA8-381548DA9AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"660d1f2064bf903e3b7861a285323155041bd769","datavalue":{"value":{"entity-type":"item","numeric-id":5249582,"id":"Q5249582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$B17530E5-A00B-4374-8398-A812DA728484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320d5893f9326747288b78ee6523f14c9647fbf2","datavalue":{"value":{"entity-type":"item","numeric-id":6041769,"id":"Q6041769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$A66A73B4-0B65-4A62-9209-F5491550E4FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9ea266d9b11e8237f6961e5be7b93c1a2b9ffd2","datavalue":{"value":{"entity-type":"item","numeric-id":2135266,"id":"Q2135266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$45279907-74A0-4C31-B27A-76DA5367147C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4e8be7330aa010ae7cfcbb8d06cd66ec512bbc","datavalue":{"value":{"entity-type":"item","numeric-id":5096999,"id":"Q5096999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$26E2A25B-497C-4FCA-8915-F6267D36FE6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226ac51af7d93f154c3f8b7fe0edd6b66219d452","datavalue":{"value":{"entity-type":"item","numeric-id":6109918,"id":"Q6109918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6183756$29A1159C-D9E7-4D25-8485-034E377FE22F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a18d465c5e542a674a333d27a156a82f730c1e6","datavalue":{"value":"10.1214/23-AOS2305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6183756$AE197256-798D-481D-B83F-01083138D00B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c6f007d4769fc52b99dbab4558735fa8c253e93","datavalue":{"value":{"entity-type":"item","numeric-id":6041769,"id":"Q6041769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56e1188755f7f14978fabda45bb8492fd141724e","datavalue":{"value":{"amount":"+0.8498119115829468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6183756$44DF7309-BB5A-4DFF-B3E2-EA58CF478E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc18fe4e36b144f4fe20394d8afad171e531cd56","datavalue":{"value":{"entity-type":"item","numeric-id":6202672,"id":"Q6202672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fc0c2f64bb6be057469f48f8f2c7cf23411128d","datavalue":{"value":{"amount":"+0.8177537322044373","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6183756$9C6B07FD-E5E3-46C5-8893-7D804BABED43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77b426de1069b5d74af0bee837b09f77bac8e180","datavalue":{"value":{"entity-type":"item","numeric-id":2660385,"id":"Q2660385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fec9a074b5beee240739c5aeedbadaf542dc4aa3","datavalue":{"value":{"amount":"+0.8058527708053589","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6183756$4B134F12-A45F-4BE7-A9AB-59C7D2C01EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1fe57af99abd3ff8ac3932b77de30c78992b4f9","datavalue":{"value":{"entity-type":"item","numeric-id":5093855,"id":"Q5093855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9341028bdd9dda9b4f886b16564722ddc2690c9e","datavalue":{"value":{"amount":"+0.7874904870986938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6183756$AAFF832B-E583-4D94-8323-B51CD3FCCE92","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6183756","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6183756"}}}}}