This article considers spectral community detection in the regime of sparse networks with heterogeneous degree distributions, for which we devise an algorithm to efficiently retrieve communities. Specifically, we demonstrate that a conveniently parametrized form of regularized Laplacian matrix can be used to perform spectral clustering in sparse networks, without suffering from its degree heterogeneity. Besides, we exhibit important connections between this proposed matrix and the now popular non-backtracking matrix, the Bethe-Hessian matrix, as well as the standard Laplacian matrix. Interestingly, as opposed to competitive methods, our proposed improved parametrization inherently accounts for the hardness of the classification problem. These findings are summarized under the form of an algorithm capable of both estimating the number of communities and achieving high-quality community reconstruction.
翻译:文章考虑了在分布程度不一的分散网络体系下对光谱群落的探测,为此,我们设计了一种有效检索社区的算法。具体地说,我们证明,可以使用一种简便的平衡化的固定的拉普拉西亚矩阵形式在分散的网络中进行光谱聚集,而不会受到其程度的异质性的影响。此外,我们展示了这一拟议矩阵与目前流行的非回溯性矩阵、贝西-赫西安矩阵以及标准的拉普拉西亚矩阵之间的重要联系。 有趣的是,与竞争性方法相反,我们提出的改进的平衡化模式本身就说明了分类问题的难度。 这些结论以能够估计社区数量和实现高质量社区重建的算法形式总结。