基于初始划分的标签传播社区发现算法  

Community Discovery Algorithm with the Label Propagation Based on the Initial Division

作　　者：翁伟[1] 林琛[2] 朱顺痣[1] 马樱[1] 邹权[2] 陈泽红[1] 

机构地区：[1]厦门理工学院计算机与信息工程学院,福建厦门361024 [2]厦门大学信息科学与技术学院,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2015年第1期107-113,共7页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(61373147);福建省教育厅A类项目(JA13238);厦门市科技计划项目(3502Z20133041);厦门理工学院对外科技合作交流专项(E201301300)

摘　　要：采用标签传播算法进行社区发现时间效率高,无需人工参数,但容易产生精度限制的问题.研究了启发式的标签传播算法,快速地进行社区的初始划分,大量减少了初始标签的个数,进行标签迭代传播来修正初始划分得到最终的社区.理论分析和实验证明这种方法在不增加时间复杂度的情况下,提高了准确率,并有效消除了精度限制的现象.The label propagation algorithm for community discovery enjoys high time efficiency and does not need artificial parameters,but it is prone to the resolution-limit problem.A new heuristic label propagation algorithm is studied.The central idea lies in accelerating the initial division of the community first,obtaining a significant reduction in the number of initial tag,and then correcting the initial division to achieve the final divided societies by iteration of the label propagation.Theoretical analysis and experimental results show that the method improves the accuracy and effectively eliminates the phenomenon of resolution-limit problem without increasing the time complexity.

关 键 词：标签传播 社区发现 精度限制问题 

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