论文标题
匹配相关随机图的恢复阈值
Matching recovery threshold for correlated random graphs
论文作者
论文摘要
对于两个相关图，它们是从一个共同的erdős-rényi图$ \ mathbf {g}（n，p）$中独立子采样的，我们希望从这两个图形\ emph {无标签}的观察中恢复其\ emph {littent} pertex。当$ p = n^{ - α+o（1）} $对于$α\ in（0，1] $中时，我们为是否可以正确匹配正面的正面分数，建立了一个尖锐的信息理论理论阈值。我们的结果在WU，XU和YU的最新工作中持续不断的因素。
For two correlated graphs which are independently sub-sampled from a common Erdős-Rényi graph $\mathbf{G}(n, p)$, we wish to recover their \emph{latent} vertex matching from the observation of these two graphs \emph{without labels}. When $p = n^{-α+o(1)}$ for $α\in (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.
