Matching recovery threshold for correlated random graphs

05/29/2022

∙

by   Jian Ding, et al.

∙

0

∙

share

For two correlated graphs which are independently sub-sampled from a common Erdős-Rényi graph 𝐆(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.