The Geometry of Community Detection via the MMSE Matrix

Abstract

The information-theoretic limits of community detection have been studied extensively for network models with high levels of symmetry or homogeneity. In this talk, Reeves will present a new approach that applies to a broader class of network models that allow for variability in the sizes and behaviors of the different communities, and thus better reflect the behaviors observed in real-world networks. The results show that the ability to detect communities can be described succinctly in terms of a matrix of effective signal-to-noise ratios that provides a geometrical representation of the relationships between the different communities. This characterization follows from a matrix version of the I-MMSE relationship and generalizes the concept of an effective scalar signal-to-noise ratio introduced in previous work.

This work can be found online at https://arxiv.org/abs/1907.02496