The Power of Side-information in Subgraph Detection - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2017

The Power of Side-information in Subgraph Detection

Le Pouvoir d'Information Supplementaire en Detection des Sousgraphes

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et 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)

Identifiants

Citer

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⟩
541 Consultations
282 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More