动态网络桥系数增量聚类算法  

Discovering communities in dynamic networks:a bridgeness incremental clustering algorithm

作　　者：王玙[1,2] 高琳[1] 

机构地区：[1]西安电子科技大学计算机学院,陕西西安710071 [2]西安电子科技大学经济管理学院,陕西西安710071

出　　处：《西安电子科技大学学报》2013年第1期30-35,共6页Journal of Xidian University

基　　金：国家自然科学基金重点资助项目(60933009);国家自然基金重大研究计划资助项目(91130006);西安电子科技大学基本科研业务费资助项目(K5051106004);陕西省社科基金资助项目(11M016)

摘　　要：提出了一种在动态网络中发现社团结构的增量式聚类算法.基于动态网络中相邻采样时刻网络拓扑变化较小的特点,将网络前一时刻的社团结构作为当前时刻的初始聚类结果,利用边的桥系数判断网络拓扑变化对聚类结果的影响,局部调整初始聚类,最终得到符合当前网络拓扑的社团结构.通过和马尔可夫聚类算法进行比较,验证了本算法的精确性和高效性.实验结果表明,利用增量聚类算法分析动态网络,避免了对当前网络的重新聚类,可以快速、准确地发现动态网络社团结构.An incremental clustering algorithm is proposed to identify community structures in dynamic networks.Based on the feature that in dynamic networks there is little change in adjacent network snapshots,the community structures detected in last snapshot are used as the initial clustering results in current snapshot.Then the edge bridgeness is adopted to judge the snapshot change＇s influence on clustering results.Finally,the community structures fitting current snapshot are obtained by locally modifying the initial clustering results.The accuracy and efficiency of our algorithm are validated by comparing with the MCL algorithm.Experimental results demonstrate that our approach performs accurately and effectively in identifying community structures in dynamic networks because clustering the current snapshot can be avoided by incrementally analyzing the dynamic networks.

关 键 词：复杂网络 社团结构 聚类算法 增量聚类 桥系数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]