Estimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade

Abstract

We study the inference of a planted dense component in a sparse random graph from a single spreading process. The graph has an Erd\H{o}s-R\'enyi background with edge probability $p_n$ and contains a planted dense component of size $n^{\alpha}$, with $\alpha>1/2$, whose internal edge density $\xi>0$ is constant. The edge set is unobserved; the data only consist of the successive infection times from a single realization of a continuous-time SI process with independent and exponentially distributed transmission times. We show that the planted dense component leaves a detectable signature in the spreading process: after the exploration enters the dense component, it undergoes a short phase of accelerated growth. By analyzing this phase, we localize its onset and endpoint. These localization results yield consistent estimators of the component-size exponent $\alpha$, the background edge density $p_n$, and the internal edge density $\xi$ from the infection times alone. When the identities of the infected vertices are also observed, we further establish consistent recovery of the planted dense component.