集合扩充的社团分解算法

Community decomposition algorithm based on set expansion

社团结构是复杂网络的重要特征之一,寻找网络中的社团对于分析整个网络的结构和功能都有非常重要的意义.综述了一些经典的复杂网络社团结构划分的算法,提出了一种基于集合扩充的社团结构划分的新算法.该算法以网络中相邻的两个节点构成的集合为起点,用社团同外部联系的边的数目与社团内部边的数目的比值作为度量指标,通过计算将某一个邻居节点加入该集合后度量指标值的变化情况来判断某个邻居节点是否加入该集合,若度量指标值变小则将该邻居节点加入该集合,若度量指标值变大则不将该邻居节点加入该集合,直到不再有新的邻居节点加入时,一个社团就被划分出来.在剩下的网络中重复这个过程直到网络中的节点完全被划分.用社团结构分解中的两个经典例子测试了该算法,从测试结果来看,用该方法能够合理地划分网络中的社团结构,且运算量小,运行效率高,达到了预期目标.该社团结构的划分方法对于规模较大的复杂网络也具有普遍意义.

Community structure is one of important characteristics in complex network,seeking communities has very important meaning in the analysis of structure and function of the whole network.On the basis of some classical complex network structure partition algorithms,a new community structure partition algorithm based on set expansion was proposed.In this work,we defined an indicator,which is the ratio of the number of edges internal and external community.In the proposed algorithm,the set was originally composed of two adjacent nodes,indicator was recalculated if a neighbor node joined the set.Set was expanded when the indicator decreased.A community was detected until there was no new neighbor node to join.Other communities in the network were detected by repeating this process.This algorithm was implemented to detect communities in two classical networks.Experimental results show that this algorithm can reasonably detect communities with little computation and high efficiency.Moreover,the proposed algorithm can be generalized to other largescale complex networks.