The Geometry of Community Detection via the MMSE Matrix
The Geometry of Community Detection via the MMSE Matrix
复制标题
DOI：
10.1109/isit.2019.8849594
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
G. Reeves;Vaishakhi Mayya;A. Volfovsky
中科院分区：
文献类型：
--
作者：
G. Reeves;Vaishakhi Mayya;A. Volfovsky
对于具有高度对称性或同质性的网络模型，社区检测的信息论极限已经被广泛研究。本文的贡献是研究一类更广泛的网络模型，这些模型允许不同社区的大小和行为的可变性，从而更好地反映在现实世界网络中观察到的行为。我们的结果表明，检测社区的能力可以用有效信噪比矩阵简洁地描述，该矩阵提供了不同社区之间关系的几何表示。这一特征源于I-MMSE关系的矩阵版本，并推广了先前工作中引入的有效标量信噪比的概念。我们给出了逐节点互信息的渐近公式和最小均方误差的上界。理论结果得到了数值模拟的支持。
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.