Side Information in Recovering a Single Community: Information Theoretic Limits



Journal Title

Journal ISSN

Volume Title


Institute of Electrical and Electronics Engineers Inc.


In this paper, we study the effect of side information on the information limits of recovering a hidden community of size K inside a graph consisting of n nodes with K = o(n). Side information for each node in the graph is modeled by a random vector whose components have finite cardinality. The variation in quantity of side information as a function of graph size n is represented by varying the size of the vector of side information while keeping the log-likelihood ratio (LLR) of each component with respect to the node labels fixed. We show when and by how much side information can improve the information limits of weak and exact recovery by providing tight necessary and sufficient conditions for both weak and exact recovery. Furthermore, we show that, under certain conditions, any algorithm achieving weak recovery can also achieve exact recovery if followed by a local voting procedure. © 2018 IEEE.


Full text access from Treasures at UT Dallas is restricted to current UTD affiliates (use the provided Link to Article).


Stochastic processes, Information theory, Computational complexity, Graph theory

This work was supported in part by the NSF grant 1718551.


©2018 IEEE