基于相似度的社区发现算法研究-计算机软件与理论专业毕业论文.docx

独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其它个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名:日期: 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于 保密□,在 年解密后适用本授权书。不保密□。(请在以上方框内打“√”)学位论文作者签名: 指导教师签名:日期: 年 月 日 日期: 年 月摘要在许多真实的网络中都存在模块或社区。社区的检测是社会网络学习的重要的课题,对于我们了解社会网络的内部关系和结构,进而应用到与社会网络相关的很多领域都有重要的意义。传统的基于相似度的社区发现算法比如GN算法在计算的时候时间复杂度非常高,而基于相似度的社区发现算法的结果主要取决于相似度的选择,有些相似度选择可能使得结果更准确,但是针对规模较大的网络,时间也要是考虑的主要因素之一,所以可以根据网络的不同要求来选择相似度的不同度量方法。目前基于相似度的算法中有两个经典算法,分别是GN算法以及AP算法。GN算法中的时间复杂度非常高,针对这个弱点,可以提出一种基于扩散核特征矩阵相似度的分裂算法和一种基于DSD相似度的分裂算法。这两个算法都是基于网络拓扑结构的算法,避免了GN算法中的计算边介数的时间复杂度高的弱点。实验的结果表示,两个算法的划分效果和GN算法差不多,在效率上有很大的提高,对于相似度的度量方法的研究有一定的价值。Newman贪婪算法是近期社区发现的一个主要算法,拥有准确快速的特点,但是当社区规模过大时,可能会使得社区规模分配不均。在比较基于扩散核特征矩阵的相似度和基于DSD相似度度量方法的优缺点之后,M算法),M算法快速准确的优点,M算法的社区规模分配不均匀的情况。关键词:社会网络,社区发现,相似度,,,suchastheGNalgorithm,plexityisveryhigh,,works,plexityalsohavetobeoneofthemainfactorstoconsider,,,,munitydetectionalgorithm,-mentioned,Malgorithm,toacertainextent,:munitydiscovery,similarity,modularity目录摘要.................................................................................................................IAbstract............................................................................................................、目的与意义.......