Answers are grounded in this paper and cite their sources.
The problem of detecting edge correlation between two Erdős-Rényi random graphs on <tex-math notation="LaTeX">n </tex-math> 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 <tex-math notation="LaTeX">G(n, p) </tex-math> (so that their marginal distributions are the same as the null). We establish a sharp information-theoretic threshold when <tex-math notation="LaTeX">p = n^-α +o(1) </tex-math> for <tex-math notation="LaTeX">α ∈ (0, 1] </tex-math> 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.
No takes yet. Share an insight, caveat, or question.
Ding et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: