Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator
This addresses a fundamental graph matching problem in network analysis, with incremental contributions to specific graph models.
The paper tackles the problem of estimating latent vertex correspondence between two edge-correlated random graphs with inhomogeneous structure, showing that the $k$-core estimator can achieve exact or partial recovery under certain conditions, with results applied to models like correlated stochastic block models.
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.