基于局部路径的社团发现算法

社团结构是复杂网络最重要的特性之一。针对复杂网络的社团结构发现问题,提出一种基于局部路径的相似性度量方法,并结合层次聚类算法用于社团结构发现。相对全局的相似性度量,所提的相似性度量具有较小的计算复杂度;同时又能很好地刻画网络的结构特征,克服了传统局部相似性度量在某些情形下对节点相似性的低估倾向。在合成和真实世界的网络上进行了实验,并与典型算法进行了比较,实验结果证明了所提算法的可行性和有效性。

Community Detection AIgorithm Based on LocaI Paths

Community structure is one of the most important characteristics of the complex network. With respect to community structure detection of the complex network, this paper proposes a method for measuring similarity on the basis of local path, which together with hierarchical clustering algorithm is used for the purpose of community structure detection. Compared to the measurement of global similarity, the proposed similarity measurement with a low computation complexity can describe the structural characteristics of the networks in a very good way, thus overcoming the problem of under-estimating node similarity which exists with the traditional measurement of local similarity on some occasions. The proposed method is tested on both synthesized and real-world networks, and is compared with typical algorithms in community detection. Experimental results prove the feasibility and validity of the proposed algorithm.