Barber Michael J, Clark John W
Foresight & Policy Development Department, Austrian Institute of Technology (AIT) GmbH, 1220 Vienna, Austria.
Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Aug;80(2 Pt 2):026129. doi: 10.1103/PhysRevE.80.026129. Epub 2009 Aug 28.
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.
我们研究了最近提出的用于识别网络社区的标签传播算法（LPA）。我们将LPA重新表述为一个等价的优化问题，给出一个目标函数，其最大值对应于社区解决方案。通过考虑目标函数的性质，我们识别出标签传播方法在概念和实际方面的缺点，最重要的是目标函数值的增加与所发现社区质量的提高之间的差异。为了解决这些缺点，我们修改了优化问题中的目标函数，产生了各种受约束传播标签的算法；特别值得关注的是一种最大化社区质量模块化度量的变体。讨论了所提出算法的性能特性和实现细节。同时考虑了二分网络和单分网络。
