Random Subgraph Detection Using Queries

arXiv:2110.00744v5 Announce Type: replace-cross
Abstract: The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on $n$ vertices. Under the null hypothesis, the graph is a realization of an Erd\H{o}s-R\'{e}nyi graph with edge probability (or, density) $q$. Under the alternative, there is a subgraph on $k$ vertices with edge probability $p>q$. The statistical as well as …

abstract arxiv cs.ds cs.it cs.lg detection graph hypothesis math.it math.st null observe queries random stat.th testing the graph type