基于图压缩的重叠社区发现技术研究

《基于图压缩的重叠社区发现技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于图压缩的重叠社区发现技术研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：王雪赵宇海副教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2014年6月论文答辩日期：2014年6月21日2014年7月答辩委员会主席：乔建忠教授于亚新副教授李晓光教授东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyResearchofOverlappingCommunityDetectionB

2、asedonGraphCompressionByWangXueSupervisor：AssociateProfessorZhaoYuhaiNortheasternUniversity，June2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢=出■思。学位论文作者签名：乏j殇日期：Wf眵，

3、易．可7学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年0学位论文作者签名：签字日期：砂f％．导师签名：黝詹签字日期：捌铱g、纠∥VPf’f锡』多砂、，D万方数据东北大学硕士学位论文捅要基于图压缩的重叠社区发现技术研究摘要近年来，寻找复杂网络中的

4、社区结构已经成为复杂网络中研究的热点，社区发现问题也因此成为近年复杂网络领域中的热门问题。由于现实存在的网络社区通常并不是绝对彼此独立的，而是彼此重叠的，并且重叠社区可以反映更加真实的网络结构，因此关于重叠社区发现问题的讨论也成了复杂网络中的研究重点。本文先从社区发现的研究背景、意义出发，通过介绍基本理论知识，引出社区结构的概念，随后综述了近年来社会网络中社区结构的研究成果，介绍了目前主要的重叠社区发现算法，并对它们的优缺点进行了对比与分析。针对大多数现有的重叠社区发现算法在应用大规模网络时效率较低的问题，本文基

5、于图压缩提出一个新的重叠社区发现算法，能在保证准确度的前提下，数量级地提高在单机上处理的网络规模，进而发现重叠社区。首先，通过基于图压缩的社区结构表示模型一一凝聚图，来对网络进行无损压缩。然后，在凝聚图上基于种子迭代的思想，通过不断优化社区适应度函数来对种子进行扩展。当种子的社区适应度达到最大时，便形成社区。最后，再将相似度很高的社区进行合并，得到最终的重叠社区结果。由于压缩后的凝聚图大大降低了网络复杂程度，并且能在一定程度上减少重复计算，因此这种方法可以大大提高计算效率。本文实验部分从算法的有效性、效率以及重叠

6、节点的准确性三个方面来对算法进行分析和验证。实验证明，本文提出的算法不但可以使发现的重叠社区趋于合理化，而且大大提高了单机上能够处理的网络规模，使有效解决大规模网络上的重叠社区发现问题成为可能。关键词：社会网络；图压缩；社区发现；重叠社区；种子扩展万方数据东北大学硕士学住论文摘要万方数据东北大学硕士学位论文AbstractResearchofOverlappingCommunityDetectionBasedonGraphCompressionAbstractInrecentyears，findingcommun

7、itystructureincomplexnetworkshasbeenahotareaofresearchandthereforecommunitydetectionhasbecomeahotissueinthefieldofcomplexnetworks．Socialcommunitiesinrealityarenotmostlyindependentofoneanother,butoverlappingeachother．Sinceoverlappingcommunitycanreflectthenetwo

8、rkstructuremorerealistic，overlappingcommunitydetectionhasbecometheresearchfocusofcomplexnetworks．Inthisthesis，wefirstintroducethebasictheoriesandknowledgeofcommunitydetectionsuchastheconc