复杂网络上的社团结构探测研究

《复杂网络上的社团结构探测研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湘潭大学硕士学位论文复杂网络上的社团结构探测研究姓名：项炬申请学位级别：硕士专业：理论物理指导教师：唐翌20080516摘要近年来复杂网络研究受到了来自物理以及其它学科的研究者的广泛关注，成为当今的一个研究热点。大量研究已经表明在真实世界中各种不同的复杂网络具有许多共同的结构特征，例如小世界性质、无标度性、社团结构等。我们对复杂网络的社团结构及其探测方法进行了研究。在复杂网络中社团结构的存在意味着网络通常由若干个社团组成，在这些社团内节点之间的连接相对紧密，而各个社团之间的连接则比较的稀疏。网络的这种结构特征对网络的动力学有着重要影响，并且在真实网络中这些社团通常对应着

2、某种功能单元如社会网络中真实的社会分组、WWW上内容相关的网页、或论文引用网络中关于某个主题的论文。因此，探测分析网络的社团结构对我们认识和理解真实复杂网络的结构以及功能有着重要意义。目前，已经有许多研究者投身到社团结构探测的研究当中并提出了各种各样的算法以便能够快速而准确的找到网络中的社团，但是探测算法的时间复杂度和准确性之间的矛盾仍然是大规模复杂网络的社团结构分析面临的重要问题。在本文中，我们系统分析了已有的社团探测算法，然后设计了一种改进社团探测算法准确性的方案，并根据这个方案，提出了一类改进的社团探测算法。本文共分为五章。在第一章我们对复杂网络的研究进行了回顾，

3、并介绍了本文的主要研究内容。在第二章，我们介绍了复杂网络的主要结构特征，并系统介绍了复杂网络的社团结构，包括社团的定义、社团结构探测、以及社团划分的评价。在第三章中我们系统分析了已有的一些社团探测算法及其性能。同时，根据研究的需要我们研究了这些算法如何扩展到加权网络，以及在考虑加权网络的内在边权之后算法的探测能力的变化。根据前一章的分析，我们在第四章中首先设计了一个改进社团探测算法精度的方案，然后据此提出了一类改进的Girvan-Newman算法，并在计算机产生的具有已知社团结构的网络以及一些真实网络上测试了这些算法。测试的结果显示无论是在计算机产生的网络上还是在真实网

4、络上改进后的算法都要比原算法有更优异的表现。另外，我们还将改进的算法扩展到了具有内在权重的网络；测试的结果显示同样是考虑了内在边权，改进算法的权重版本要胜过原算法的权重版本。这些结果说明我们对算法的进行改进的尝试是成功的，同时也证实了我们的改进方案的可行性。第五章对本文的工作进行了总结，并对本领域的研究进行了展望。关键词：复杂网络；社团结构；Girvan-Newman算法；边介数；边聚类系数IAbstractComplexnetworkshaverecentlyreceivedextensiveattentionfromphysicsandotherdiscipline

5、s.Alotofexperimentalfindingshaveuncoveredthatcomplexnetworksinvariousfieldssharemanycommonstructuralpropertiessuchassmall-worldproperty,scale-freefeature,communitystructureetc.Inthethesis,westudiedthedetectionandcharacterizationofthecommunitystructureinnetworks.Theemergenceofcommunitystr

6、uctureincomplexnetworksmeansthatnetworksoftenconsistofgroupsofverticeswithinwhichconnectionsaredensewhilebetweenwhichtheyaresparser.Suchapropertyofnetworksmayplayanimportantroleindynamicsofnetworks,ontheotherhand,communitiesinnetworksoftencorrespondsuchfunctionalunitsasrealsocialgrouping

7、sinsocialnetworks,setsofpagesonrelatedtopicsontheWWW,orsetsofrelatedpapersonasingletopicincitationnetworks.Thus,detectingandanalyzingthesecommunitiesinnetworkswillhelpusunderstandthestructureandfunctionofrealcomplexnetworksmoreeffectively.Inordertodetectcommunitiesinnetwo