Subelj Lovro, Bajec Marko
Faculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Mar;83(3 Pt 2):036103. doi: 10.1103/PhysRevE.83.036103. Epub 2011 Mar 8.
Label propagation has proven to be a fast method for detecting communities in large complex networks. Recent developments have also improved the accuracy of the approach; however, a general algorithm is still an open issue. We present an advanced label propagation algorithm that combines two unique strategies of community formation, namely, defensive preservation and offensive expansion of communities. The two strategies are combined in a hierarchical manner to recursively extract the core of the network and to identify whisker communities. The algorithm was evaluated on two classes of benchmark networks with planted partition and on 23 real-world networks ranging from networks with tens of nodes to networks with several tens of millions of edges. It is shown to be comparable to the current state-of-the-art community detection algorithms and superior to all previous label propagation algorithms, with comparable time complexity. In particular, analysis on real-world networks has proven that the algorithm has almost linear complexity, O(m¹·¹⁹), and scales even better than the basic label propagation algorithm (m is the number of edges in the network).
标签传播已被证明是一种在大型复杂网络中检测社区的快速方法。最近的进展也提高了该方法的准确性；然而，通用算法仍然是一个未解决的问题。我们提出了一种先进的标签传播算法，该算法结合了两种独特的社区形成策略，即社区的防御性保存和进攻性扩展。这两种策略以分层方式结合，以递归提取网络的核心并识别须状社区。该算法在两类带有植入划分的基准网络以及23个从具有数十个节点的网络到具有数千万条边的网络的真实世界网络上进行了评估。结果表明，该算法与当前最先进的社区检测算法相当，并且优于所有先前的标签传播算法，同时具有相当的时间复杂度。特别是，对真实世界网络的分析证明，该算法几乎具有线性复杂度O(m¹·¹⁹)，并且比基本标签传播算法扩展性更好（m是网络中的边数）。
