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

提出了一种在动态网络中发现社团结构的增量式聚类算法.基于动态网络中相邻采样时刻网络拓扑变化较小的特点,将网络前一时刻的社团结构作为当前时刻的初始聚类结果,利用边的桥系数判断网络拓扑变化对聚类结果的影响,局部调整初始聚类,最终得到符合当前网络拓扑的社团结构.通过和马尔可夫聚类算法进行比较,验证了本算法的精确性和高效性.实验结果表明,利用增量聚类算法分析动态网络,避免了对当前网络的重新聚类,可以快速、准确地发现动态网络社团结构.

Discovering communities in dynamic networks:a bridgeness incremental clustering algorithm

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.