Ecole d'ingénieur et centre de recherche en Sciences du numérique

The power of side-information in subgraph detection

Kadavankandy, Arun; Avrachenkov, Konstantin; Cottatellucci, Laura; Sundaresan, Rajesh

Research Report RR-8974, February 2017

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ős-Rényi (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 sideinformation. 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.

Document Arxiv Hal Bibtex

Titre:The power of side-information in subgraph detection
Mots Clés:Belief Propagation, Dense community detection, Cavity Method, Detectability, Stochastic Block Model
Type:Rapport
Langue:English
Ville:
Date:
Département:Systèmes de Communication
Eurecom ref:5157
Copyright: © INRIA. Personal use of this material is permitted. The definitive version of this paper was published in Research Report RR-8974, February 2017 and is available at :
Bibtex: @techreport{EURECOM+5157, year = {2017}, title = {{T}he power of side-information in subgraph detection}, author = {{K}adavankandy, {A}run and {A}vrachenkov, {K}onstantin and {C}ottatellucci, {L}aura and {S}undaresan, {R}ajesh}, number = {EURECOM+5157}, month = {03}, institution = {Eurecom}, url = {http://www.eurecom.fr/publication/5157},, }
Voir aussi: