Detecting network communities by propagating labels under constraints
Detecting network communities by propagating labels under constraints
复制标题
DOI：
10.1103/physreve.80.026129
复制
发表时间：
2009-08-01
影响因子：
2.4
通讯作者：
Clark, John W.
中科院分区：
文献类型：
--
作者：
Barber, Michael J.;Clark, John W.
我们研究了最近提出的用于识别网络社区的标签传播算法（LPA）。我们将LPA重新表述为一个等价的优化问题，给出一个目标函数，其最大值对应于群体解。通过考虑目标函数的性质，我们识别了标签传播方法在概念上和实践上的缺陷，最重要的是增加目标函数的值和提高所发现社区的质量之间的差异。为了解决这些缺点，我们修改了优化问题中的目标函数，产生了各种算法，这些算法在约束条件下传播标签；特别令人感兴趣的是一种变体，它可以最大化社区质量的模块化度量。讨论了所提出算法的性能特性和实现细节。考虑了二部网络和单部网络。
We investigate the recently proposed label-propagation algorithm (LPA) for identifying network communities. We reformulate the LPA as an equivalent optimization problem, giving an objective function whose maxima correspond to community solutions. By considering properties of the objective function, we identify conceptual and practical drawbacks of the label-propagation approach, most importantly the disparity between increasing the value of the objective function and improving the quality of communities found. To address the drawbacks, we modify the objective function in the optimization problem, producing a variety of algorithms that propagate labels subject to constraints; of particular interest is a variant that maximizes the modularity measure of community quality. Performance properties and implementation details of the proposed algorithms are discussed. Bipartite as well as unipartite networks are considered.