基于相似度的社区发现算法与研究 (1).pdf

分类号学号 M200972391 学校代码1 0 4 8 7 密级硕士学位论文基于相似度的社区发现算法研究学位申请人:伍星宇学科专业:计算机软件与理论指导教师:李国徽教授答辩日期:2012年1月 A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering Similarity-munity Detection Algorithm Candidate : Wu Xingyu Major : Computer Softwareand theory Supervisor :LiGuohui Huazhong University of Science and Technology Wuhan 430074, January, 2012 独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其它个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名: 日期: 年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□,在_____年解密后适用本授权书。不保密□。(请在以上方框内打“√”) 学位论文作者签名: 指导教师签名: 日期: 年月日日期: 年月 I 华中科技大学硕士学位论文摘要在许多真实的网络中都存在模块或社区。社区的检测是社会网络学习的重要的课题,对于我们了解社会网络的内部关系和结构,进而应用到与社会网络相关的很多领域都有重要的意义。传统的基于相似度的社区发现算法比如GN算法在计算的时候时间复杂度非常高,而基于相似度的社区发现算法的结果主要取决于相似度的选择,有些相似度选择可能使得结果更准确,但是针对规模较大的网络,时间也要是考虑的主要因素之一,所以可以根据网络的不同要求来选择相似度的不同度量方法。目前基于相似度的算法中有两个经典算法,分别是GN算法以及AP算法。GN算法中的时间复杂度非常高,针对这个弱点,可以提出一种基于扩散核特征矩阵相似度的分裂算法和一种基于DSD相似度的分裂算法。这两个算法都是基于网络拓扑结构的算法,避免了GN算法中的计算边介数的时间复杂度高的弱点。实验的结果表示,两个算法的划分效果和GN算法差不多,在效率上有很大的提高,对于相似度的度量方法的研究有一定的价值。 Newman贪婪算法是近期社区发现的一个主要算法,拥有准确快速的特点,但是当社区规模过大时,可能会使得社区规模分配不均。在比较基于扩散核特征矩阵的相似度和基于DSD相似度度量方法的优缺点之后,使用DSD相似度度量算法结合 M算法),M算法快速准确的优点,而且在一定程度上 M算法的社区规模分配不均匀的情况。关键词:社会网络,社区发现,相似度,模块度 II 华中科技大学硕士学位论文 Abstract In many munity structure is a natural feature. munity detection in works has e an important problem in the study work. It can enhance the insight into the intrinsicstructure works, andis of great significance to many related fields of works. munity detectionalgorithm based on similarity algorithm, such as the GNalgorithm, whose plexity is very high, can not be applied plex networks. The result of munity detection algorithm based on similarity measure depends on the choice of similarity. May be some similarity selection makes the result more accurate, but for works, the ple