Detection Threshold for Correlated Erdős-Rényi Graphs via Densest Subgraph
Jian Ding, Hang Du · IEEE Transactions on Information Theory · 2023
The problem of detecting edge correlation between two Erdős-Rényi random graphs on$n$unlabeled nodes can be formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are sampled independently; under the alternative, the two graphs are independently sub-sampled from a parent graph which is Erdős-Rényi$\mathbf {G}(n, p)$(so that their marginal distributions are the same as the null). We establish a sharp information-theoretic threshold when$p = n^{-\alpha +o({1)}}$for$\alpha \in (0, 1]$which sharpens a constant factor in a recent work by Wu, Xu and Yu. A key novelty in our work is an interesting connection between the detection problem and the densest subgraph of an Erdős-Rényi graph.