The Geometry of Community Detection via the MMSE Matrix

Journal Article

The information-theoretic limits of community detection have been studied extensively for network models with high levels of symmetry or homogeneity. The contribution of this paper is to study 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. Our 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. We provide explicit formulas for the asymptotic per-node mutual information and upper bounds on the minimum mean-squared error. The theoretical results are supported by numerical simulations.

Full Text

Duke Authors

Cited Authors

  • Reeves, G; Mayya, V; Volfovsky, A

Published Date

  • July 1, 2019

Published In

Volume / Issue

  • 2019-July /

Start / End Page

  • 400 - 404

International Standard Serial Number (ISSN)

  • 2157-8095

Digital Object Identifier (DOI)

  • 10.1109/ISIT.2019.8849594

Citation Source

  • Scopus