基于局部相似性的复杂网络社区发现方法

Complex Network Community Detection by Local Similarity

复杂网络是复杂系统的典型表现形式,社区结构是复杂网络最重要的结构特征之一.针对复杂网络的社区结构发现问题,本文提出一种新的局部相似性度量,并结合层次聚类算法用于社区结构发现.相对全局的相似性度量,本文提出的相似性度量具有较低的计算开销;同时又能很好地刻画网络的结构特征,克服了传统局部相似性度量在某些情形下对节点相似性的低估倾向.为了将局部相似性度量用于社区结构发现,推广了传统的Ward层次聚类算法,使之适用于具有相似性度量的任意对象,并将其用于复杂网络社区结构发现.在合成和真实世界的网络上进行了实验,并与典型算法进行了比较,实验结果表明所提算法的可行性和有效性.

Complex networks are a typical form of representation of complex systems. Community structure is one of the most important structural characteristics of complex networks. In this paper,we propose a new measurement of similarity based on local structures for the purpose of detecting communities in complex networks. Compared to the similarity measures based on the entire network,the proposed similarity measure requires less computation and produces good descriptions of the structural characteristics of the networks. Meanwhile,it reverses the tendency of under-estimating produced by some existing similarity measures based on local structures. To utilize our measurement of similarity to the detection of community structures,we also generalize the Ward hierarchical clustering algorithm so that it is applicable to any object that has similarity measurement. And as an application we particularly employ this algorithm to detect community structures in complex networks. The proposed method is tested on both computer-generated and real-world networks,and is compared with the typical algorithms in community detection. Experimental results verify and confirm the feasibility and validity of the proposed method.