复杂网络中的社团结构分析算法研究综述

An Overview of Algorithms for Analyzing Community Structure in Complex Networks

许多实际网络中都存在着社团结构。为了寻找大规模复杂网络中的社团结构,人们提出了很多算法。本文综述了近几年来比较有代表性的一些算法。首先介绍了计算机科学中最有名的谱平分法和Kernighan-Lin算法,然后介绍了社会学中具有代表性的分裂算法和凝聚算法,并着重分析了最新提出来的一种寻找网络中彼此重叠的社团结构的派系过滤算法。最后指出了进一步的研究方向。

Community structure exists in many real networks.In recent years,a lot of algorithms have been proposed to find communities in large-scale complex networks.In this paper,we review some representative algorithms.Two famous algorithms in computer science,spectral bisection method and KernighanLin algorithm,are first introduced.Some representative sociological approaches including divisive and agglomerative method are then investigated.In particular,a new clique percolation method to uncovering the overlapping communities in complex networks is introduced.Finally,some future directions are pointed.