Advanced modularity-specialized label propagation algorithm for detecting communities in networks
Advanced modularity-specialized label propagation algorithm for detecting communities in networks
复制标题
DOI：
10.1016/j.physa.2009.12.019
复制
发表时间：
2010-04-01
影响因子：
3.3
通讯作者：
Murata, T.
中科院分区：
文献类型：
--
作者：
Liu, X.;Murata, T.
最近提出了一种用于网络社区检测的模块化标签传播算法（LPAm）。这种有前途的算法提供了一些理想的品质。然而，LPAm有利于社区划分，其中所有社区在总度上都是相似的，因此它很容易陷入模块化空间中的局部最大值。为了避免局部最大值，我们采用了多步贪婪凝聚算法（MSG），可以合并多对社区在同一时间。结合LPAm和MSG，我们提出了一种先进的模块化专用标签传播算法（LPAm+）。实验表明，LPAm+成功地检测到社区具有更高的模块化值比以往任何时候都报告在两个常用的现实世界的网络。此外，LPAm+在准确性和速度之间提供了一个公平的折衷。(C)2009 Elsevier B.V.保留所有权利。
A modularity-specialized label propagation algorithm (LPAm) for detecting network communities was recently proposed. This promising algorithm offers some desirable qualities. However, LPAm favors community divisions where all communities are similar in total degree and thus it is prone to get stuck in poor local maxima in the modularity space. To escape local maxima, we employ a multistep greedy agglomerative algorithm (MSG) that can merge Multiple pairs of communities at a time. Combining LPAm and MSG, we propose an advanced modularity-specialized label propagation algorithm (LPAm+). Experiments show that LPAm+ successfully detects communities with higher modularity values than ever reported in two commonly used real-world networks. Moreover, LPAm+ offers a fair compromise between accuracy and speed. (C) 2009 Elsevier B.V. All rights reserved.