pipette
ESEspañol

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

Maximilien Dreveton, Paula M\"urmann, Patrick Thiran

Preprint

In the authors' words

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 and contains a planted dense component of size , with , whose internal edge density 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 , 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.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.