论文标题
稀疏随机块模型的共同信息
Mutual information for the sparse stochastic block model
论文作者
论文摘要
我们考虑了在随机块模型中恢复社区结构的问题。我们的目的是描述稀疏制度中观察到的网络与实际社区结构之间的相互信息，在稀疏状态下，节点的总数差异，而给定节点的平均程度保持界限。我们的主要贡献是对该数量极限的猜想，我们根据概率度量的汉密尔顿 - 雅各比方程表示，这表达了这一点，并且证明了该猜想极限为渐近互助提供了下限。汉密尔顿 - 雅各比方程的适合性是在我们的同伴论文中获得的。在社区之间的链接比社区内的联系更有可能的情况下，已知渐近互信息由变分公式给出。我们还表明，在这种情况下，我们的猜想与此公式相吻合。
We consider the problem of recovering the community structure in the stochastic block model with two communities. We aim to describe the mutual information between the observed network and the actual community structure in the sparse regime, where the total number of nodes diverges while the average degree of a given node remains bounded. Our main contributions are a conjecture for the limit of this quantity, which we express in terms of a Hamilton-Jacobi equation posed over a space of probability measures, and a proof that this conjectured limit provides a lower bound for the asymptotic mutual information. The well-posedness of the Hamilton-Jacobi equation is obtained in our companion paper. In the case when links across communities are more likely than links within communities, the asymptotic mutual information is known to be given by a variational formula. We also show that our conjectured limit coincides with this formula in this case.
