基于最短路径和最大模块度融合的社团发现算法

Detecting Community Structures by Shortest Path and Maximum Modularity

复杂网络已成为当前的一个研究热点,复杂网络具有许多重要性质,其中社团结构是复杂网络最普遍最重要的拓扑性质之一。目前已有很多流行的网络社团挖掘算法,但是大部分社团挖掘算法存在准确性低、适用范围窄等缺陷,为了克服这些缺点,本文结合社团挖掘的相关研究,提出一种基于改进近邻传播的社团挖掘算法。首先采用最短路径计算任意节点对之间的距离,并运用近邻传播算法初步识别中心点;然后基于模块度优化的思想,建立"中心点过滤"数学模型,自动识别网络的社团结构;最后对本算法在一些广泛使用的网络数据上进行性能测试。测试结果表明,本算法与传统方法相比,具有适用范围广、准确率高、容忍分辨极限能力强等优点。

With the development of the research on complex networks, people have found many important properties about them. The community structure is one of the most popular and the most important topological properties of complex networks. So far, a large number of algorithms have been proposed to detect community structures in complex networks, but most of them are suitable for a specific network structure. Based on the previous research, this paper puts forward a kind of improved algorithm based on Affinity Propagation. First of all, dissimilarity distance matrix is calculated by using the shortest path algorithm. Then the exem- plars are identified by the Affinity Propagation algorithm. Finally, based on the maximum modularity and minimum variation, ＂Community centers filtering＂ model is established to automatically identify the community structure of the network. Experimental results on real datasets, show that the proposed algorithm, comparing with the traditional method, has higher perfoormnce related to the accuracy, and the ability to tolerate the resolution limit.