一种优化标签传播过程的重叠社区发现算法*

随着社区规模的不断扩大，基于标签传播思想的重叠社区发现算法得到较大发展。经典重叠社区发现算法虽然很好的利用了标签随机传播特性实现了重叠社区发现，但是也导致该算法输出结果很不稳定、社区生成质量较差。本文的主要贡献在于，采用最新的ClusterRank为所有节点排序降低随机性带来的结果稳定性差的弊端；引入最大社区节点数以控制最大社区节点数目防止远大于其他社区的Monster出现。采用真实数据集和人工网络验证，结果证实，改良后算法可行有效。

Overlapping communities detection during the process of improvement of label propagation

With the expansion of community size, overlapping community detection algorithm based on label propagation gains a promising expectation. Classic overlapping community finding algorithm makes good use of label random propagation characteristics in order to achieve overlap community discovery. However, it results in unstable output of algorithm and poor community production quality. The main contribution of this paper is that, using the latest ClusterRank to sort all nodes reduces the disadvantages of random results of stability; node number of the largest community is introduced to control the maximum number of community node to prevent those which are much larger than the Monster appearing in other communities. The real-world data sets and artificial network authentication confirm that the improved algorithm is feasible and effective.