基于模块度最大化的社区发现算法的研究

《基于模块度最大化的社区发现算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTER’SDISSERTATION论文题目基于模块度最大化的社区发现算法的研究作者姓名万云学科专业计算机科学与技术指导教师陈晶副教授2016年5月中图分类号：TP393学校代码：10216UDC：004密级：公开工学硕士学位论文基于模块度最大化的社区发现算法的研究硕士研究生：万云导师：陈晶副教授申请学位：工学硕士学科专业：计算机科学与技术所在单位：信息科学与工程学院答辩日期：2016年5月授予学位单位：燕山大学ADissertationinComputerScienceandTechnologyRES

2、EARCHONCOMMUNITYDETECTIONBASEDONMODULARITYMAXIMIZATIONbyWanYunSupervisor:ProfessorChenJingYanshanUniversityMay,2016燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《基于模块度最大化的社区发现算法的研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中

3、以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日摘要摘要随着网络的迅速发展，对复杂网络的研究在许多领域都备受关注。社区结构是复杂网络的一个普遍特征，对社区结构的挖掘成为了网络分析中的研究热点。复杂网络由许许多多个社区构成，社区发现对于了解复杂网络中的社区结构有着重要的意义。从计算角度而言，社区划分相当于将任务分解，可以降低计算复杂度；从实际应用而言，社区发现“产生”了推荐，方便了人们的生活。本文针对社区发现问题，结合社区结构这个重要属性，利用模块度最大化方法对社区发现算法中的时间复杂度以及社区结

4、构的强弱展开了深入研究。首先，针对基于模块度最大化这类标签传播算法中时间复杂度高的问题，本文依据“先传播，后合并”的原则，降低了社区合并导致整个网络需要更新带来的较高时间复杂度；结合社区结构的概念提出了基于模块度最大化的标签传播算法CDMM-LPA。基于社区结构的重要性，本文将社区结构作为一个重要的考虑因素融入CDMM-LPA算法中，使得最终获得的社区属于强结构社区。其次，提出了基于模块度最大化的双向合并的社区发现算法CDPM。CDPM算法是基于混合式合并的社区发现的改进算法。该算法通过计算节点之间的相似度，减少算法初

5、始阶段生成的子社区数目。通过检查生成的社区是否含有弱结构社区来决定CDPM算法的运行次数，避免了通过设置参数来控制算法的执行次数，从而降低了CDPM算法的时间复杂度。最后，基于真实网络数据集和模拟生成的网络数据集，验证并分析了两种算法的可行性。关键词：复杂网络；模块度；社区结构；标签传播；社区发现I燕山大学工程硕士学位论文AbstractWiththerapiddevelopmentofthesocialnetwork,theresearchofcomplexnetworkshasattractedmuchattent

6、ioninmanyareas.Ascommunitystructureisregardedasacommonfeatureofthecomplexnetwork,miningcommunitystructurebecomesaresearchhotspotinthenetworkanalysis.Acomplexnetworkiscomposedofanumberofcommunities,andcommunitydetectionisofgreatsignificancetounderstandthecommunit

7、ystructure.Fromtheviewofthecalculation,communitydivisioncandecomposethelargescaletasktoreducethecomputationalcomplexity.Whileinthepracticalapplication,therecommendationinapplicationsisbasedoncommunitydetection.Andcommunitydetectionfacilitatespeople'slives.Inthis

8、paper,theresearchonthetimecomplexityandthestrengthofcommunitystructureisbasedonthemethodofmodularitymaximizationandtheimportantattributeofcommunitystructure.Firstly,“