2022/03/28 by Jian Ding, Ding, Jian, Hang Du +1 · 1 citation
Computer Science · Decision Sciences · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Probability (math.PR) #Probability and Risk Models #Statistics Theory (math.ST) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2203.14573
openalex publication_date 2022/03/28 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
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 G(n, p) (so that their marginal distributions are the same as the null). We establish a sharp information-theoretic threshold when p = n-α+o(1) for α∈ (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.