Matching recovery threshold for correlated random graphs
The Annals of Statistics · 2023 · Volume 51 · Issue 4
Abstract
For two correlated graphs which are independently sub-sampled from a common Erdős–Rényi graph G(n,p), we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p=n−α+o(1) for α∈(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.
Keywords
05C80, 68Q87, Correlated Erdős–Rényi random graph, information threshold, matching recovery
Enable JavaScript for citation tools and additional paper interactions.