复杂网络社区挖掘——改进的层次聚类算法

Community detection in complex networks-an improved hierarchical clustering algorithm

社区挖掘算法研究是复杂网络分析领域的热点问题。传统层次聚类算法在复杂网络社区挖掘过程中,需要计算所有顶点对之间的相似度。针对这一缺点,在详述了常见相似度计算方法和顶点重要性度量方法的基础上,将ego角色的探测过程引入层次聚类算法,而后只计算其他顶点与ego顶点之间的相似度,提高了社区挖掘效率。最后在不同类型的现实网络中验证了算法的有效性。

Community detection has been a hot topic in the analysis of complex networks. Traditional hierarchical clustering algorithm has to compute each pair of vertices in the process of community detecting.To address this weakness,after the description of normal similarity calculation method and measures of the centrality of vertices,a ego actor detecting process added to the hierarchical clutering method, then only compute similarity between ego vertex and other vertices,to improve the efficiency of community detecting. Finally, real network experiments show that this improved algorithm is effective.