三种经典复杂网络社区结构划分算法研究_时京晶

《三种经典复杂网络社区结构划分算法研究_时京晶》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第19卷第4期电脑与信息息技技术术2011Vol．1年89月No．42011年8月ComputerandInformationTechnologyAug．2011文章编号：1005－1228（2011）04－0042－02三种经典复杂网络社区结构划分算法研究1,2时京晶（1.长安大学信息工程学院，陕西西安710064；2.西藏民族学院信息工程学院，陕西咸阳712082）摘要：社团结构是复杂网络的重要特征之一。针对复杂网络中社团划分问题，文章给出了三种经典的社团划分算法，阐述了各种算法的基本原理，并对各算法进行了适当的

2、分析和比较，为实际应用中社团划分算法的选择提供了参考。关键词：复杂网络；社区结构；Laplace图谱；Kernighan-Lin算法；GN算法中图分类号：TP393文献标识码：ATheResearchofThreeTypicalCommunityDetectionAlgorithmsinComplexNetworks1,2SHIJing-jing(1．SchoolofinformationEngineering,Chang’anUniversity,Xi’an710064,China;2.Schoolofinform

3、ationEngineering,TibetNationalitiesInstitute,Xianyang712082,China)Abstract：Communitystructureisoneofimportantcharacteristicsofcomplexnetworks.Forcommunitydetectionincomplexnetworks,thispaperpresentsthreetypicalcommunitydetectionmethods,describesthebasicprincipl

4、eofeachmethodanddoessomeanalysisandcomparisonamongthem.Thepurposeofallworksinthispaperistosupplysomeusefulreferenceforcommunitydetectionalgorithmselectioninactualapplications.Keywords:complexnetworks;communitystructure;Laplacegraphspectrum;Kernighan-Linalgorith

5、m;GNalgorithm现实生活中存在着各种各样的网络系统，如人际区代表针对同一主题的相关论文；万维网中的社区就关系网、合作网、交通运输网、计算机网等。网络模型是讨论相关主题的若干网站；生物化学网络或者电子是描述这些复杂系统的最有效模型。通过对现实系电路网络中的社区则可能是某一类功能单元。发现这统网络模型的研究，人们发现许多现实系统的网络些网络中的社区有助于研究人员更加有效地理解和开模型是介于完全规则和完全随机之间的。由于这种发这些网络。网络是真实复杂系统的拓扑抽象，因此它被称为复杂网络。[1]复杂网络是复杂系统的

6、高度抽象，除具备小世界、[2]无标度等重要特性外，还拥有另外一个重要特征，即[3]社区结构特性，也就是说，整个网络是由若干个“群（group）”或“团（cluster）”构成的。每个群内部的节点之间的连接相对非常紧密，但是各个群之间的连接相对来说却比较稀疏，如图1所示。图中的网络包含三个社团，分别对应图中三个圆圈包围的部分。在这些社团内部，节点之间的联系非常紧密，而社团之间的联系就稀疏的多。图1一个小型的具有社团结构性质的网络在大型复杂网络中进行社区搜寻或发现社区，具网络社团结构的研究起源于社团学，已经有很长有重要的

7、实用价值，如：社会网络中的社区代表根据兴的历史。它与计算机科学中的图形分割和社会学中的趣或背景而形成的真实的社会团体；引文网络中的社分级聚类有着密切的关系。目前，关于复杂网络中的社收稿日期：2011-03-22作者简介：时京晶（1983-）,女,陕西咸阳人,硕士,主要研究方向：复杂网络理论应用、网络信息检索、数字视频处理。第19卷第4期时京晶：三种经典复杂网络社区结构划分算法研究·43·区发现算法已有很多，这些方法的核心思想、执行效如果图G可以被分解成g个子图，但子图之间存率、使用范围等方面差别较大。本文着重叙述了三

8、种典在少量连接时，其相应的Laplace矩阵L就不再是一型的复杂网络社区识别算法，Kernighan-Lin算法、个分成g块的对角阵。此时，对应0这个特征值就只有Laplace图特征值的谱二分法和GN算法，并对此三种一个特征向量I。但是，在0的附近还有g-1个比0稍方法进行了适当的分析和比较。大的特征值，并且这g-1个特征值相应的特征向量可（k