The Power of Side-information in Subgraph Detection - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2017

The Power of Side-information in Subgraph Detection

Le Pouvoir d'Information Supplementaire en Detection des Sousgraphes

(1, 2) , (2) , (3) , (4)


In this work, we tackle the problem of hidden community detection. We consider Belief Propagation (BP) applied to the problem of detecting a hidden Erd\H{o}s-R\'enyi (ER) graph embedded in a larger and sparser ER graph, in the presence of side-information. We derive two related algorithms based on BP to perform subgraph detection in the presence of two kinds of side-information. The first variant of side-information consists of a set of nodes, called cues, known to be from the subgraph. The second variant of side-information consists of a set of nodes that are cues with a given probability. It was shown in past works that BP without side-information fails to detect the subgraph correctly when an effective signal-to-noise ratio (SNR) parameter falls below a threshold. In contrast, in the presence of non-trivial side-information, we show that the BP algorithm achieves asymptotically zero error for any value of the SNR parameter. We validate our results through simulations on synthetic datasets as well as on a few real world networks.
Fichier principal
Vignette du fichier
RR-8974v4.pdf (717.92 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01394889 , version 1 (10-11-2016)
hal-01394889 , version 2 (10-11-2016)
hal-01394889 , version 3 (23-11-2016)
hal-01394889 , version 4 (06-03-2017)



Arun Kadavankandy, Konstantin Avrachenkov, Laura Cottatellucci, Rajesh Sundaresan. The Power of Side-information in Subgraph Detection. [Research Report] RR-8974, Inria Sophia Antipolis. 2017, pp.37. ⟨hal-01394889v4⟩
512 View
265 Download



Gmail Facebook Twitter LinkedIn More