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

We study the inference of a planted dense component in a sparse random graph from a single spreading process. The graph has an Erdős-Rényi background with edge probability pn and contains a planted dense component of size nα, with α>1/2, whose internal edge density ξ>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 α, the background edge density pn, and the internal edge density ξ 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.