Learning Erd\H{o}s-R\'enyi Random Graphs via Edge Detecting Queries

MaRDI QIDQ6318443zbMATH OpenFDO

Authors Zihan Li, Matthias Fresacher, Jonathan Scarlett

Publication date 8 May 2019

Has companion code repository https://github.com/scarlett-nus/er_edge_det

Abstract: In this paper, we consider the problem of learning an unknown graph via queries on groups of nodes, with the result indicating whether or not at least one edge is present among those nodes. While learning arbitrary graphs with $n$ nodes and $k$ edges is known to be hard in the sense of requiring $Omega(min{k}^{2}logn,n^2)$ tests (even when a small probability of error is allowed), we show that learning an ErdH{o}s-R'enyi random graph with an average of $$ edges is much easier; namely, one can attain asymptotically vanishing error probability with only $$ tests. We establish such bounds for a variety of algorithms inspired by the group testing problem, with explicit constant factors indicating a near-optimal number of tests, and in some cases asymptotic optimality including constant factors. In addition, we present an alternative design that permits a near-optimal sublinear decoding time of $$.

This page was built for publication: Learning Erd\H{o}s-R\'enyi Random Graphs via Edge Detecting Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318443)