基于局部信息的重叠社团发现算法研究

《基于局部信息的重叠社团发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学号M201072340学校代码10487密级硕士学位论文基于局部信息的重叠社团发现算法研究学位申请人苏联钦：学科专业：计算机软件与理论指导教师：袁凌副教授答辩日期：2013.1.31AThesisSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringResearchonOverlappingCommunityDetectionAlgorithmsBasedonLocalInformationCandidate:SuLianqinMajor:ComputerSoftwareand

2、TheorySupervisor:Assoc.Prof.YuanLingHuazhongUniversityofScience&TechnologyWuhan430074,P.R.ChinaJanuary,2013独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其它个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位

3、论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□，在_____年解密后适用本授权书。不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学硕士学位论文摘要现实世界中许多系统都可以用复杂网络来表示，社团结构是许多实际复杂网络中都存在的一个特征。探索复杂网络中的社团结构，可以帮助我们了解网络的内部结构和特性，进而发现网络中存在的规律，预测网络的行为

4、和功能。因而，复杂网络中的社团发现得到越来越多人的关注。目前，研究者们已经对社团发现投入大量的研究，提出了一系列的社团发现算法。社团发现方法可大致分为全局社团发现和局部社团发现。局部社团发现依据节点的局部拓扑信息，在降低时间和空间的消耗上具有很大的扩展性。同时，现实中的许多复杂网络系统中，节点往往具有多个属性，使得节点可能属于多个社团，因而基于局部信息的重叠社团发现具有更大的实用价值。Newman提出基于贪婪思想的Newman快速算法，同时提出评价社团划分质量的标准——模块度。Clauset等人在该算法的基础上，引入堆的数据结构计算和更新模块度，提出新的算法CNM算法。算法时间复杂度接近

5、线性，适用于大规模网络。但CNM算法由于使用全局模块度优化发现社团，存在难以发现小社团的问题。由Radicchi等人提出的弱社团是一种定义比较小的社团定义，网络中满足弱社团定义的社团有很多，因此会发现大量的弱社团。但是弱社团也是一种有实际意义且被许多学者认可的社团定义。在研究和学习社团发现算法的基础上，提出LCNM算法，解决CNM算法难以发现小社团问题。使用LFM算法中提出的基于局部信息的局部适应度函数发现网络中的弱社团，将大量的弱社团集构成新的网络作为CNM算法的输入。由于一个节点可能对多个弱社团都有较大的适应度值可以被划分到多个弱社团，所以LCNM算法还能发现重叠社团结构。最后在人工

6、数据集和真实数据集上进行实验，实验结果证明LCNM算法能解决CNM算法难以发现小社团问题还能发现重叠社团，并具有较高的效率和较大的模块度值。关键词：复杂网络社团发现模块度局部适应度弱社团结构I华中科技大学硕士学位论文ABSTRACTManyrealworldsystemscanberepresentedascomplexnetworks.CommunityStructurehasbeenfoundasanimportantpropertyofthesereal-worldcomplexnetworks.Detectionofcommunitystructurecanhelpusknowt

7、heinnerstructureandcharacteristicsofnetworks,findtheregularexistinthenetworksandthenforecasttheactionandfunction.Withtheresultthan,moreandmorepersonpaycloseattentiontothecommunitydetectionofcomplexnetworks.Recentyears,