论文标题
稀疏图中光谱聚类的统一框架
A unified framework for spectral clustering in sparse graphs
论文作者
论文摘要
本文考虑了具有异构度分布的稀疏网络政权中的光谱社区检测，为此，我们设计了一种算法来有效检索社区。具体而言，我们证明了一种方便的参数化形式的正则化laplacian矩阵可用于在稀疏网络中执行光谱聚类，而不会遭受其程度的异质性。此外，我们在该提出的矩阵与现在流行的非折线矩阵，贝特·赫西亚矩阵以及标准的拉普拉斯矩阵之间表现出重要的联系。有趣的是，与竞争方法相反，我们提出的改进的参数化固有地解释了分类问题的硬度。这些发现是以算法的形式汇总的，能够估计社区数量和实现高质量的社区重建。
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.
