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

Nonrandom Community Detection Algorithm Based on Label Propagation

作　　者：刘功申[1] 张浩霖 孟魁[1] 苏波[1] 

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240

出　　处：《上海交通大学学报》2015年第8期1168-1173,1180,共7页Journal of Shanghai Jiaotong University

基　　金：国家重点基础研究发展规划(973)项目(2013CB329603);国家自然科学基金项目(61472248;61171173)资助

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

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

分 类 号：TP399[自动化与计算机技术—计算机应用技术]