资源描述：
《复杂网络的社区结构.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8卷第1期复杂系统与复杂性科学Vol.8No.12011年3月COMPLEXSYSTEMSANDCOMPLEXITYSCIENCEMar.2011文章编号:16723813(2011)01005714复杂网络的社区结构程学旗,沈华伟(中国科学院计算技术研究所,北京100190)摘要:社区结构作为真实复杂网络所普遍具有的一个重要拓扑特性,在最近10年内得到了广泛而深入的研究。回顾了近几年国内外社区结构研究的主要进展,重点介绍社区发现的研究历程和研究成果,并结合社会计算的背景展望了社区结构研究的未来发展方向和潜在的应用价值。关键词:社区结构;社区发现;模块
2、度;社会计算中图分类号:N94文献标识码:ACommunityStructureofComplexNetworksCHENGXueqi,SHENHuawei(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China)Abstract:Asacommonandimportanttopologicalcharacteristicofrealworldcomplexnetworks,communitystructurehasbeenextensivelystudiedi
3、nthelastdecade.Thispaperreviewsthemainprogressesinthescientificresearchoncommunitystructure.Especially,thispaperdescribesthedevelopmentatthedetectionofcommunitystructurefromvariousdisciplines.Finally,thispaperdiscussesthefutureresearchdirectionsofthecommunitystructureandthepotential
4、applicationsinsocialcomputing.Keywords:communitystructure;communitydetection;modularity;socialcomputing0引言真实世界中的许多复杂系统可以表示成图或网络,包括社会网络、信息网络、生物网络和技术网络[16]等。经验分析表明,这些复杂网络可以自然地分成一些节点组,使同一个节点组内的两个节点之间比不同节点组的两个节点之间更倾向于有边相连,网络的这种拓扑特性被称为社区结构,相应地,每个节点组被[6]称为一个社区。社区结构刻画了网络中连边关系的局部聚集特性,也体现了
5、网络中连边的分布不均匀性。进一步,网络中的社区通常由功能相近或性质相似的网络节点组成,因此,社区被认为有助于揭示网络结构和功能之间的[79]关系。以万维网(WorldWideWeb)为例,通过超链接紧密关联的网页形成一个个的社区,同一个社区的[34]网页具有相近的话题。社区结构的示例如图1所示。收稿日期:20101029基金项目:国家自然科学基金(60873245,60933005)作者简介:程学旗(1971),男,研究员,博导,主要研究方向为网络科学、海量信息检索和数据挖掘、社会计算、分布式计算和网络模拟仿真。58
6、复杂系统与复杂性科学2011年3月针对社区结构的研究大体上可以分为3个类型:社区发现、社区演化分析,及社区结构与网络动力学和网络压缩表示等功能性特征之间的关系。其中,社区发现是基础和核心的研究问题,吸引了很多领域学者们的关注。近年来,研究人员从连边密度、渗流、信息论、图聚类、优化、同步、扩散等不同的视角,提出了很多社区发现方法,这些方法相应地都在一些特定的网络上[531]获得了成功应用。对社区发现方法的综合性介绍和对比分图1社区结构示例[11][3234]析可以参照一些社区发现算法的综述。众多社区发现方法的提出,为我们提供了充分的选择自由,同
7、时由于缺乏各个方法适用性分析以及方法间优劣的对比,也使我们在根据具体的应用需求选择相应方法时面临着诸多困惑。另外,目前研究人员对网络社区认识上的差异仍然存在。由于一般的社区定义仅仅是定性的,长期以来,人们对社区的定量定义进行了大量尝试。但仍然没有哪一种社区的定量定义得到广泛的认可。网络社区的重叠、多尺度、异质等问题的提出使社区结构的研究变得更加复杂。同时,人们逐步致力于把社区结构的研究从具有单一类型节点、单一类型连边关系的网络扩展到具有多种类型节点和连边关系的网络上,包括有向网络、带权网络、二部图网络、多部图网络、具有多样性关系的网络甚至超图等。受限于带时间属
8、性的持续化数据获取困难以及社区定义和社
