Planting trees in graphs, and finding them back

MaRDI QIDQ6309229zbMATH OpenFDO

Authors Laurent Massoulié, Ludovic Stephan, Don Towsley

Publication date 5 November 2018

Abstract: In this paper we study detection and reconstruction of planted structures in ErdH{o}s-R'enyi random graphs. Motivated by a problem of communication security, we focus on planted structures that consist in a tree graph. For planted line graphs, we establish the following phase diagram. In a low density region where the average degree $lambda$ of the initial graph is below some critical value $lambd{a}_c=1$, detection and reconstruction go from impossible to easy as the line length $K$ crosses some critical value $f(lambda)ln(n)$, where $n$ is the number of nodes in the graph. In the high density region $lambda>lambd{a}_c$, detection goes from impossible to easy as $K$ goes from $o(sqrtn)$ to $omega(sqrtn)$, and reconstruction remains impossible so long as $K=o(n)$. For $D$-ary trees of varying depth $h$ and $2leDleO(1)$, we identify a low-density region $lambda<lambd{a}_D$, such that the following holds. There is a threshold $h\ast =g(D)ln(ln(n))$ with the following properties. Detection goes from feasible to impossible as $h$ crosses $h\ast$. We also show that only partial reconstruction is feasible at best for $hgeh\ast$. We conjecture a similar picture to hold for $D$-ary trees as for lines in the high-density region $lambda>lambd{a}_D$, but confirm only the following part of this picture: Detection is easy for $D$-ary trees of size $omega(sqrtn)$, while at best only partial reconstruction is feasible for $D$-ary trees of any size $o(n)$. These results are in contrast with the corresponding picture for detection and reconstruction of {em low rank} planted structures, such as dense subgraphs and block communities: We observe a discrepancy between detection and reconstruction, the latter being impossible for a wide range of parameters where detection is easy. This property does not hold for previously studied low rank planted structures.

This page was built for publication: Planting trees in graphs, and finding them back

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