Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs

Dong Huang, Xianwen Song, Pengkun Yang

This paper studies the problem of recovering the hidden vertex correspondence between two correlated random graphs. We propose the partially correlated Erdős-Rényi graphs model, wh…