基于最少中心节点覆盖的社区发现方法

Least Core Nodes Covering Based Community Detect Method

复杂网络社区发现目前已成为计算机科学、生物学、社会学等多个领域研究热点之一。为快速准确地发现大规模网络中社区结构,该文提出一种基于中心节点覆盖的社区发现算法。算法以拥有最多邻居节点的中心节点开始,依次找到能覆盖整个网络节点的最少中心节点,然后以这些中心节点作为小社区,计算相交小社区间合并度量分值,每次合并两个具有最大合并度量分值的小社区,并以模块性Q值作为全局最优合并序列评价函数,全局最大Q的合并序列,即为最优社区划分结构。实验结果表明,算法对网络社区结构划分的时间复杂度为nlogn（n为网络节点数目）并具有较高准确率。

Complex network community discovery has become one of the hot issues in many fields, including computer science,biology, sociology, etc. In order to quickly and accurately find the community structure of large-scale network, this paper presents a discovery algorithm based on center node whose neighbors node can cover the whole network. The algorithm starts with the most central node whose neighbor nodes can cover entire network then define them as initial small communities, then calculate the combining measure scores between these cross communities pair, each time we will merge a pair of cross communities which get the most combining measure score, and modularity Q value as a global optimal evaluation function for the merge sequence, one merge sequence which achieve maximum Q is the optimal community structure partition of the network. As described, the algorithm can even divided into a dense network into communities with approximately linear time complexity.Applying the algorithm on several typical community social networks shows that the algorithm is of great accuracy and low time complexity.