Matching recovery threshold for correlated random graphs
研究了从同一个Erdős–Rényi随机图中独立子采样得到的两个相关图，在无标签条件下恢复潜在顶点匹配的信息论阈值，适用于图匹配和网络对齐领域。
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.