基于单步添加团的重叠社团检测算法

An Overlapping Community Detection Algorithm Based on Addtion of a Clique at Each Step

基于局部扩充的重叠社团检测算法由单个节点或团出发,不断添加新的节点而获得最终的社团划分,但现有算法均为每次添加一个节点,没有充分考虑所添加节点的局部信息,从而影响了社团检测结果的准确性.为此,文中提出了一种基于单步添加团的重叠社团检测算法,该算法从一个团开始,通过不断添加此团邻居内适应度增值最大的团,使算法在局部扩充时不仅考虑了所添加节点与已有社团的连接紧密性,而且考虑了所添加节点内部的连接情况.在真实网络和计算机生成网络上的实验结果表明,与现有基于局部扩充的重叠社团检测算法相比,文中算法可以更准确地检测出复杂网络中的重叠社团.

The local expansion-based overlapping community detection algorithms start from a single node or a clique, and then repeatedly add a new node to the obtained community, thus obtaining the final community. How- ever, the existing local expansion-based overlapping community detection algorithms always add one node at each step, so the local information of the added nodes has not been fully considered, thus reducing the accuracy of the algorithms. In order to solve this problem, an overlapping community detection algorithm is proposed, which adds a clique at each step. This algorithm starts from a clique, and expands the clique by repeatedly adding a clique of the largest fitness value in the neighborhood. In this way, the links between the added node and the existing community and the links between the added nodes are both taken into account. An empirical evaluation on the synthetic and real datasets demonstrates that the proposed algorithm can detect the overlapping communities in complex networks more accurately than the existing algorithms.