论文标题
通过密度子图形的相关Erdős-rényi图的检测阈值
Detection threshold for correlated Erdős-Rényi graphs via densest subgraphs
论文作者
论文摘要
在$ n $未标记的节点上检测两个ERDőS-Rényi随机图之间的边缘相关性的问题可以作为假设检验问题进行表述：在无原假设下，两个图是独立采样的；在替代方案下，这两个图是从eRdős-rényi$ \ mathbf {g}（n，p）$（以使它们的边际分布与null相同的父级）独立采样。当$ p = n^{ - α+o（1）} $（0，1] $）$ p = n^{ - α+o（1）$时，我们建立了一个清晰的信息理论阈值，这在我们作品的最新作品中加强了一个不变的因素。我们工作中的关键新颖性是检测问题与eRddős-rényi的浓度范围之间有趣的连接。
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^{-α+o(1)}$ for $α\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.
