Side Information in Recovering a Single Community: Information Theoretic Limits

Abstract

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.