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ő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.
Related
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Graphon Hawkes Processes: Sparse Estimation and Network Recovery
- Weighted Score Matching on Bounded Domains: Nonparametric Density Estimation and Interaction Graph Recovery
- Minimax Slope Estimation and Support Recovery under Weak Gaussian Selection
- A polyhedral framework for hierarchical Archimedean copulas: estimation, hierarchy recovery and singular asymptotics
BibTeX
@misc{dreveton2026estimation,
title = {{Estimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade}},
author = {Maximilien Dreveton and Paula Mürmann and Patrick Thiran},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08766},
eprint = {2610.08766},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08766},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Estimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade
AU - Maximilien Dreveton
AU - Paula Mürmann
AU - Patrick Thiran
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08766
UR - https://arxiv.org/abs/2610.08766
AB - 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 p_n 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 p_n, 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.
ER -