基于极大团的重叠社区发现算法的研究与实现

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

1、万方数据分类号UDC密级学位论文基于极大团的重叠社区发现算法的研究与实现作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：张楠于戈教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：杨晓春鲍玉斌夏秀峰东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryResearchandImplementationofOverlappingCommunityDetectionbasedonMaxim

2、alCliquesByZhangNanSupervisor：ProfessorYuGeNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：揪稀日期：2口，华．占·三乒学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的

3、规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年／一年半口两年口学位论文作者签名：苏术争签字日期：2D，弘．6．≥眵导师签名：孑戈签字日期：2D哗．Z．2夕‘万方数据东北大学硕士学住论文摘要基于极大团的重叠社区发现算法的研究与实现摘要随着复杂系统科学的不断发展以及社交网络、移动通信网络等现实网络的不断推动作用，复杂网络的研究备受关注。在研究中，学者们发现社区结构存在于复杂网络之

4、中，并且社区结构对于理解复杂网络的结构和功能有着至关重要的地位，因此，许多研究者投入到对社区结构发现的研究中，与此同时，重叠社区发现问题也成为了近年来的热门问题之一，但该问题至今仍未得到完美的解决。本文通过研读近年来具有代表性的文章，总结目前典型的重叠社区发现算法，分析其优点和不足之处，在此基础上提出了一种基于极大团的重叠社区发现算法，并对其进行了并行化的实现。首先，极大团是本文提出的重叠社区发现算法的基础，同时结合极大团结构的特点，对其枚举过程提出了4种剪枝策略，过滤掉了搜索过程中不必要的搜索，提高了搜索效率。其次，针对重叠社区发现过程中的三个

5、步骤，提出了基于重叠极大团的社区种子的选择方法；基于序列突变的项点加入策略以及基于拓扑结构的社区验证方法。这些方法在一定程度上提高了重叠社区发现的准确性和效率。最后，根据本文提出的极大团枚举算法和重叠社区发现算法，对其并行化的可行性进行了分析，同时在BSP系统上进行了并行化的实现。总之，本文主要研究了基于极大团的重叠社区发现问题，并针对其中的不足，提出了高效的解决方案。大量的实验验证了本文方案的高效性和准确性。关键词：社区结构：极大团；重叠社区发现；BSP：并行算法一II—万方数据东北大学硕士学位论文AbstractResearchandImpl

6、ementationofOverlappingCommunityDetectionbasedonMaximalCliquesAbstractWiththecontinuousdevelopmentofcomplexsystemscience，andbythepromotionofsocialnetworksandmobilecommunicationnetworks，theresearchoncomplexnetworkshasbecomemoreconcern．Manyresearcheshaveshownthatcomplexnetworka

7、reofobviouscommunitystructures，communitystructureisacrucialroleforunderstandingthestructureandfunctionofcomplexnetworks，andalargenumberofscientistshavespenthugeeffortoncommunitydetectioninthepastdecade．Atthesametime，overlappingcommunitydetectionhasbecomeoneofthepopulartopicsi

8、ncomplexnetworks．ButtheproblemisstillnotsatisfactorilysolvedBystudyi