Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator

arXiv2302.05407MaRDI QIDQ6426089FDOQ6426089

Authors: Miklós Z. Rácz, Anirudh Sridhar 

Publication date: 10 February 2023

Abstract: 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.

This page was built for publication: Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426089)