The Power of Side-Information in Subgraph Detection

DOI10.1109/TSP.2017.2786266MaRDI QIDQ4621706zbMATH OpenOpenAlexFDO

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

Publication date 12 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.04847

Graph algorithms (graph-theoretic aspects) (05C85) Detection theory in information and communication theory (94A13) Measures of information, entropy (94A17) Applications of graph theory to circuits and networks (94C15)

Abstract: In this work, we tackle the problem of hidden community detection. We consider Belief Propagation (BP) applied to the problem of detecting a hidden ErdH{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.

Cited in

(2)

This page was built for publication: The Power of Side-Information in Subgraph Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621706)