We consider the task of estimating the latent vertex correspondence between two edge-correlated random graphs with generic, inhomogeneous structure. We study the so-called \emph{$k$-core estimator}, which outputs a vertex correspondence that induces a large, common subgraph of both graphs which has minimum degree at least $k$. We derive sufficient conditions under which the $k$-core estimator exactly or partially recovers the latent vertex correspondence. Finally, we specialize our general framework to derive new results on exact and partial recovery in correlated stochastic block models, correlated Chung-Lu graphs, and correlated random geometric graphs.
翻译:我们考虑估算两个具有通用、不相容结构的边缘相关随机图之间的潜在脊椎对应物的任务。 我们研究了所谓的 emph{$k$-core spestomator}, 由此产生了一个巨大的、共同的两张至少具有最低度的图表子图的顶端对应物。 我们得出了足够的条件, 使美元核心估计物能够准确或部分恢复潜伏脊椎对应物。 最后, 我们专门设计了我们的总框架, 以获得相关随机断裂区块模型、 相关钟楼图和相关随机几何图的准确和部分恢复结果 。