非随机的标签传播社区划分算法

上海交通大学学报（自然版） ›› 2015, Vol. 49 ›› Issue (08): 1168-1173.

• 自动化技术、计算机技术 • 上一篇下一篇

非随机的标签传播社区划分算法

刘功申，张浩霖，孟魁，苏波

（上海交通大学电子信息与电气工程学院，上海 200240）

收稿日期:2014-10-08 出版日期:2015-08-31 发布日期:2015-08-31
基金资助:
国家重点基础研究发展规划（973）项目（2013CB329603），国家自然科学基金项目（61472248，61171173）资助

Nonrandom Community Detection Algorithm Based on Label Propagation

LIU Gongshen，ZHANG Haolin，MENG Kui，SU Bo

（School of Electrical Information and Electric Engineering， Shanghai Jiaotong University，Shanghai 200240， China）

Received:2014-10-08 Online:2015-08-31 Published:2015-08-31

摘要/Abstract

摘要：

摘要：针对传统社区传播算法存在局部震荡、划分结果不稳定、划分结果分辨率高等弱点，提出了非随机的标签传播社区划分算法，通过去除传统算法的随机性进而克服其弱点.该算法主要进行了3个方面的改进：按特定顺序更新节点的标签；计算标签数量时，不仅统计邻居节点，而且统计待更新节点本身；通过贡献函数避免多个最大值时的随机选择.实验证明，该算法不仅保证了算法的划分正确性，而且大幅度减少了计算过程中的随机选择动作.

关键词: 社会网络, 社区结构, 标签传播

Abstract:

Abstract： The advantages of classical community detection algorithm based on label propagation include precision and time complexity. On the other hand, there are several disadvantages, such as oscillation, unstable result, tendency of big community. The nonrandom community detection algorithm based on label propagation (NCDAL) proposed by this paper improves the disadvantages of the classical algorithm by getting rid of its random procedures. There are three improvements in the NCDAL: when renewing the label, there is the special order; when summing up the labels, both current vertex and its neighbors are counted; and when selecting the label, the contribution function is defined to avoid random selection. It is approved by the experiments that the proposed algorithm not only has high precision, but also decreases random procedures of the classical algorithm.

Key words: , social network； community structure； label propagation

中图分类号:

TP 399

刘功申，张浩霖，孟魁，苏波. 非随机的标签传播社区划分算法[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1168-1173.

LIU Gongshen，ZHANG Haolin，MENG Kui，SU Bo. Nonrandom Community Detection Algorithm Based on Label Propagation[J]. Journal of Shanghai Jiaotong University, 2015, 49(08): 1168-1173.

参考文献

［1］Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in largescale networks［J］. Physical Review E，2007，76(3)：036106.

［2］Liu X, Murata T. Advanced modularityspecialized label propagation algorithm for detecting communities in networks［J］. Physica A: Statistical Mechanics and its Applications，2010， 389(7)：14931500.

［3］赵卓翔, 王轶彤, 田家堂, 等. 社会网络中基于标签传播的社区发现新算法［J］. 计算机研究与发展，2011，48(s3)：815.

ZHAO Zhuoxiang, WANG Yitong, TIAN Jiatang, et al. A novel algorithm for community discovery in social networks based on label propagation ［J］. Journal of Computer Research and Development，2011，48(s3)：815.

［4］Leung Ian X Y, Pan Hui, Pietro Lio, et al. Towards realtime community detection in large networks［J］. Physical Review E，2009，79(6)：066107.

［5］Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities［J］. Physical Review E，2009，80(1)：016118.

［6］Newman M E J. Modularity and community structure in networks［J］. Proceedings of the National Academy of Sciences，2006，103(23)：85778582.

［7］Newman M E J, Girvan M. Finding and evaluating community structure in networks［J］. Physical Review E，2004，69(2)：026113.

［8］Newman M E J. Fast algorithm for detecting community structure in networks［J］. Physical Review E，2004，69(6)：066133.

［9］Clauset A, Newman M E J, Moore C. Finding community structure in very large networks［J］. Physical Review E，2004，70(6)：066111.

非随机的标签传播社区划分算法

Nonrandom Community Detection Algorithm Based on Label Propagation

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价