Efficiently matching random inhomogeneous graphs via degree profiles
Jian Ding, Yumou Fei, Yuanzheng Wang
The Annals of Statistics · 2025 · Volume 53 · Issue 4
Abstract
In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities between different pairs of vertices. Inspired by and extending the matching algorithm via degree profiles by Ding, Ma, Wu and Xu (2021), we obtain an efficient matching algorithm as long as the minimal average degree is at least Ω(log2n) and the minimal correlation is at least 1−O(log−2n).
Keywords
05C80, 68Q87, degree profiles, Graph matching, inhomogeneous graphs, robust algorithms
Enable JavaScript for citation tools and additional paper interactions.