pipette
ENEnglish

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

Maximilien Dreveton, Paula M\"urmann, Patrick Thiran

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.