EXIT Analysis for Community Detection
  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.
