Pujol Josep M, Béjar Javier, Delgado Jordi
Software Department, Technical University of Catalonia, Jordi Girona 1-3 A0-S106, 08034 Barcelona, Spain.
Phys Rev E Stat Nonlin Soft Matter Phys. 2006 Jul;74(1 Pt 2):016107. doi: 10.1103/PhysRevE.74.016107. Epub 2006 Jul 17.
We propose an algorithm to find the community structure in complex networks based on the combination of spectral analysis and modularity optimization. The clustering produced by our algorithm is as accurate as the best algorithms on the literature of modularity optimization; however, the main asset of the algorithm is its efficiency. The best match for our algorithm is Newman's fast algorithm, which is the reference algorithm for clustering in large networks due to its efficiency. When both algorithms are compared, our algorithm outperforms the fast algorithm both in efficiency and accuracy of the clustering, in terms of modularity. Thus, the results suggest that the proposed algorithm is a good choice to analyze the community structure of medium and large networks in the range of tens and hundreds of thousand vertices.
我们提出了一种基于谱分析和模块度优化相结合的算法，用于在复杂网络中寻找社区结构。我们算法产生的聚类结果与模块度优化文献中最好的算法一样准确；然而，该算法的主要优点是其效率。与我们算法最匹配的是纽曼的快速算法，由于其效率高，该算法是大型网络聚类的参考算法。当比较这两种算法时，就模块度而言，我们的算法在聚类效率和准确性方面均优于快速算法。因此，结果表明，所提出的算法是分析顶点数量在数万到数十万范围内的中大型网络社区结构的一个不错选择。
