The Power of Side-Information in Subgraph Detection

DOI10.1109/TSP.2017.2786266zbMATH Open1414.94850arXiv1611.04847OpenAlexW2594897711MaRDI QIDQ4621706FDOQ4621706

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)

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.

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

Mathematics Subject Classification ID

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

Cited In (1)

Mean field analysis of personalized PageRank with implications for local graph clustering

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)