基于优化标签传播算法的社区发现方法研究

Community Detection Based on the Optimized Label Propagation Algorithm

自动发现高质量的网络社区结构是当前社会网络分析研究中的热点方向之一。与现有一些网络社区结构发现算法相比，标签传播社区发现算法具有不需要指定社区数量与时间复杂度低的优点，但该算法随机排列待更新节点和随机选择候选标签的策略严重影响了算法的准确率和稳定性。为了降低标签传播算法中这两种随机性，本文提出了一种优化的标签传播算法。经在真实基准网和计算机生成网的测试表明该算法具有更好的有效性和稳定性后，我们将该算法应用在科学网博客中“图书馆、情报与文献学”领域用户的好友关系网上，有效地发现了该网络中的社区结构。

Detectinghigh quality community structure is ahot research spots in the social network. Compared with existing community detection algorithms, label propagation algorithm does not need to specify the number of community andhas low algorithm complexity. However,the random in arranging node update order and selecting candidate label affect the accuracy and stability of the algorithm seriously, hence, we put forward an optimization of label propagation algorithm based on improved stochastic strategy in this paper. The tests on real-world networks andsynthetic networks shows that our algorithm is validity and stability, then our algorithm was used on the social network of science bloggers in ＂ library, information and bibliography＂ field,and it has found out thecommunities in the social network effectively.