EXIT Analysis for Community Detection

Abstract

This paper employs the extrinsic information transfer (EXIT) method, a technique imported from the analysis of the iterative decoding of error control codes, to study the performance of belief propagation in community detection in the presence of side information. We consider both the detection of a single (hidden) community, as well as the problem of identifying two symmetric communities. For single community detection, this paper demonstrates the suitability of EXIT to predict the asymptotic phase transition for weak recovery. More importantly, EXIT analysis is leveraged to produce useful insights such as the performance of belief propagation near the threshold. For two symmetric communities, the asymptotic residual error for belief propagation is calculated under finite-alphabet side information, generalizing a previous result with noisy labels. EXIT analysis is used to illuminate the effect of side information on community detection, its relative importance depending on the correlation of the graphical information with node labels, as well as the effect of side information on residual errors.

References in corpus (9)

• Community structure in social and biological networks
• Community detection algorithms: a comparative analysis
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Thinking Fast and Slow with Deep Learning and Tree Search
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs
• Local Algorithms for Block Models with Side Information