MATCHING RECOVERY THRESHOLD FOR CORRELATED RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Ding, Jian; Du, Hang
• 署名单位: Peking University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2305
• 发表日期: 2023
• 页码: 1718-1743
• 关键词: orientability thresholds; alignment

摘要

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.