MATCHING RECOVERY THRESHOLD FOR CORRELATED RANDOM GRAPHS

被引:8
作者
Ding, Jian [1 ]
Du, Hang [1 ]
机构
[1] Peking Univ, Sch Math Sci, Beijing, Peoples R China
基金
中国国家自然科学基金;
关键词
Correlated Erdos-Renyi random graph; matching recovery; information threshold; ORIENTABILITY THRESHOLDS; ALIGNMENT;
D O I
10.1214/23-AOS2305
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
For two correlated graphs which are independently sub-sampled from a common Erdos-Renyi graph G(n, p) , we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p = n-alpha +o(1) for alpha E (0 , 1] , we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.
引用
收藏
页码:1718 / 1743
页数:26
相关论文
共 50 条
[1]  
Aldous D, 2004, ENCYL MATH SCI, V110, P1
[2]   THE DENSEST SUBGRAPH PROBLEM IN SPARSE RANDOM GRAPHS [J].
Anantharam, Venkat ;
Salez, Justin .
ANNALS OF APPLIED PROBABILITY, 2016, 26 (01) :305-327
[3]   THE CYCLE STRUCTURE OF RANDOM PERMUTATIONS [J].
ARRATIA, R ;
TAVARE, S .
ANNALS OF PROBABILITY, 1992, 20 (03) :1567-1591
[4]  
Barak B, 2019, ADV NEUR IN, V32
[5]  
Berg AC, 2005, PROC CVPR IEEE, P26
[6]  
Bozorg M, 2020, Arxiv, DOI arXiv:1907.06334
[7]  
Cain JA, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P469
[8]  
Chen SX, 2022, Arxiv, DOI arXiv:2204.13858
[9]  
Cour T., 2006, Advances in Neural Information Processing Systems, V19
[10]  
Cullina D, 2018, Arxiv, DOI arXiv:1711.06783