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

An Overview of Algorithms for Analyzing Community Structure in Complex Networks

作　　者：谢军[1] 

机构地区：[1]南京晓庄学院,江苏南京211171

出　　处：《信息通信》2010年第4期48-51,71,共5页Information & Communications

摘　　要：社团结构在复杂网络中是一种普遍存在的特征。因而在复杂网络中分析和计算出大量大规模的社团结构就显得尤为重要,学者们也提出了很多算法。本文主要概述了近年来较有代表性的一些算法,如:Kernighan-Lin算法、谱平分法和社会学中典型分析方法凝聚方法和分裂方法,着重介绍了谱平分法中的一种算法复杂度相对较小的线性时间的物理方法Wu-Huberman算法,最后指出了进一步的研究方向。Community structure is a common property thatexists in complex network..so it is important to anlayze and calculate large quantity of large-scale community structure . many algorithms have been proposed in resent years.In this paper we review some representative algorithms such as Kernighan-Lin algorithm, spectral bisection method and some repsentative sociological approaches including divisive and agglomerative method. In particular, a linner time physical method which relative complexity is small is introduced,Finally, some future directions are pointed.

关 键 词：复杂网络 社团结构 Kernighan-Lin算法 谱平分法 凝聚方法 分裂方法 Wu-Huberman算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]