复杂网络中的社团结构算法综述

《复杂网络中的社团结构算法综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第38卷第5期2009年9月电子科技大学学报JournalofUniversityofElectronicScienceandTechnologyofChinaV．01．38No．5Sep．2009复杂网络中的社团结构算法综述汪小帆，刘亚冰(上海交通大学电子信息与电气工程学院上海闵行区2002401【摘要】社团结构是复杂网络的一个极其重要的特性，网络社团结构挖掘在生物学、计算机科学和社会学等多个领域都具有很重要的意义。近年来，针对不同类型的大规模复杂网络，A'IJ'1提出了很多寻找社团结构的算法。该文综述了该领域最新的比较有代表性的一

2、些算法，重点分析了基于模块度指标的改进算法，能够体现社团层次性和重叠性的新算法，衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。关键词复杂网络；社团结构；层次性：模块度函数：重叠性中图分类号N941；TP311．13文献标识码Adoi：10．39690．issn．1001．0548．2009．05．007OverviewofAlgorithmsforDetectingCommunityStructureinComplexNetworksWANGXiao‘。fanandLIUYa-·bing(SchoolofElectronics

3、，Information＆ElectricalEngineering，ShanghaiJiaoTongUniversityMinhangShanghai200240)AbstractCommunitystructureisaveryimportantpropertyofcomplexnetworks．Detectingcommunitiesinnetworksisofgreatimportanceinbiology，computerscience，sociologyandsoon．Inrecentyears，alotofcommunitydi

4、scoveryalgorithmshavebeenproposedaimingatdifferentkindsoflargescalecomplexnetworks．Inthispaper，wereviewsomelatestrepresentativealgorithms，focusingontheimprovedmethodsbasedonthemodularityfunction，thealgorithmswhichcandetectoverlappingandhierarchicalcommunitystructureinnetwor

5、ks，andthebenchmarkindetectingcommunities．Finally，somefuturedirectionsarepointedout．Keywordscomplexnetwork；communitystructure；hierarchicalstructure；modularityfunction；overlappingcommunities网络中的社团结构⋯是指一组相互之间有着比较大的相似性而与网络中的其他部分有着很大不同的节点的群。也就是说，在社团内部，节点之间的联系非常紧密，而社团之间的联系相对而言比较稀

6、疏。寻找社团结构并对其进行分析是了解现实生活中各种网络组织结构的一种很重要的方法，并在生物学、计算机科学以及社会学等领域都有着广泛的应用【2】。如社会网络中的社团结构使得人们能够清晰地了解他们区别于其他社团的一些特质或者信仰等；在生物分子反应网络中，聚合到一起形成功能性模块的节点往往担当特定的角色或具有特定的功能。寻找网络社团结构的算法有很多，一些经典算法，如图形分割经典问题、社会学中的聚类分析等可参考【11。l基于模块度指标的改进算法社团模块度指标Q是用于刻画社团特性强弱的参数，定义如下【3】：Q=去莓(鸣一等陋q)(1)式中岛和k，是节点

7、的度值；G是节点f所属社团；m是网络总边数。当G=C，时a(C，C，)=l，否则为0。Q值在0～1之间，一般以O=0．3作为网络具有明显社团结构的下界。模块度是应用最为广泛的评判社团特性强弱的指标。对其进行优化是个NP难题，且具体的算法时间复杂度比较高，不能应用于大规模的网络。近年来提出了很多基于模块度的改进算法，这些算法或将原算法拓展到各种有向、加权网络中，或能够体现社团的层次性和重叠性，或具有较小的时间复杂度，可用于大规模网络，或解决模块度优化中存在的分辨率问题。收稿F1期：2009—06—30基会项目：围家臼然科学基金(60674045

8、，60731160629)：上海市优秀学科带头人计划(07xDl4017)作者简介：汪小帆(1967一)，男，博上，长江学者特聘教授，主要从事复杂网络分析与控制研究