Partial Recovery of Erdős-Rényi Graph Alignment via $k$-Core Alignment

Daniel Cullina, Negar Kiyavash, Prateek Mittal +1

We determine information theoretic conditions under which it is possible to partially recover the alignment used to generate a pair of sparse, correlated Erdős-Rényi graphs. To pro…