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

IEEE Transactions on Signal Processing (Vol. PP, N°99)

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-Renyi (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 a so-called 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 a suitably defined phase-transition parameter. We validate our results on synthetic datasets and a few real world networks.

Document Doi Bibtex

Titre:The Power of Side-information in Subgraph Detection
Département:Systèmes de Communication
Eurecom ref:5416
Copyright: © 2017 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @article{EURECOM+5416, doi = {}, year = {2017}, month = {12}, title = {{T}he {P}ower of {S}ide-information in {S}ubgraph {D}etection}, author = {{K}adavankandy, {A}run and {A}vrachenkov, {K}onstantin and {C}ottatellucci, {L}aura and {S}undaresan, {R}ajesh}, journal = {{IEEE} {T}ransactions on {S}ignal {P}rocessing ({V}ol. {PP}, {N}°99)}, url = {} }
Voir aussi: