基于节点相似度的网络社团检测算法研究

社团结构是众多复杂网络的统计特性之一，挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析，其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SUN，相比传统的基于边界数(betweenness)的节点分裂算法GN, SGN在速度和精度上都有明显改善;接着，在利用各种节点相似度计算方法得到节点间的相似度之后，采用几种经典的聚类分析算法对网络进行社团划分，在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法，而且对于复杂网络社团划分问题，如果选择好的网络节点相似度构造方法，已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。

Community Detection in Complex Networks Based on Vertex Similarities

One of statistical characteristics in complex networks is a community structure. Detecting communities in networks has aroused great interest among researches in recent years. Actually, community detection is very similar to the classical cluster analysis in machine learning field. Thus, the key point is how to define vertex similarities in complex networks. We first proposed an algorithm named SUN based on vertex similarities. Compared with UN, SUN is much better and faster than UN. Secondly, we used four classical clustering algorithms to detect community structure in networks based on some existing vertex similarity measures. I}he results on artificial networks and real social networks show that the similarity measures based on signal propagation and regular equivalence theory by using the whole topology structure of networks are better than the methods of Jaccard based on local vertex information. Therefore, if vertex similarities arc given well enough,proper clustering algorithms based on similarity matrices can be used to detect community structures fast and effectively in complex networks.