Louvain算法在社区挖掘中的研究与实现

《Louvain算法在社区挖掘中的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP391单位代码：11414学号：2013215071题目Louvain算法在社区挖掘中的研究与实现与实现学科专业计算机科学与技术研究方向计算机软件与理论硕士生李沐南指导教师朱丽萍副教授入学时间：2013年9月论文完成时间：2016年5月硕士学位论文独创性声明郑重声明：本硕士学位论文是作者个人在导师的指导下，独立进行研宄工作所取得的成果，。除了文中特别加以标注和致谢的地方外论文中不包含其他个人和集体己经发表或撰写的研宄成果，也不包含为获得中国石油大学或者其它单位的学位或证书所

2、使用过的材料，均己在论文中做了明。对本研宄做出贡献的个人和集体确的说明并表示了谢意。作者和导师完全意识到本声明产生的法律后果并承担相应责任。！作者签名：日期：ｙ〇ＬＬｆ，导师签名：日期：（）．ｆｊ硕士学位论文版权使用授权书本学位论文作者及指导教师完全了解中国石油大学（北京）学位论文版权使用的有关规定，使用方式包括但不限于：学校有权保留并向有关部门和机构送交学位论文的复印件和电子版；允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用影印、缩印或

3、扫描等复制手段保存和汇编学位论文；可以将本学位论文的全部或部分内容编入有关数据库进行检索。，保密期限ｉ年，解密后适用本授权书本学位论文属于保密范围。本学位论文作者如需公开出版学位论文的部分或全部内容，必须征得导师书一（面同意，且须以中国石油大学北京）为第署名单位。作者签名：ｈ？日期：ｙ〇ｉＬｆ“导师签名：评日期：＞０，“．／＜－Ｉ－摘要摘要日新月异的互联网、云计算等网络信息技术给人们的生活带来了翻天覆地的变化，人们已经逐渐踏入了大数据时代。呈指数级增长的海量数据不仅

4、为新兴的互联网企业，更为传统行业带来了机遇与挑战。网络的复杂度与规模不仅考验着现有的IT架构，也为计算机的计算能力提出了严峻的挑战。在网络社交平台盛行的今天，各大社交网站每天都会产生上TB级别的数据。传统的单机运算难以满足海量大数据处理，随着分布式计算框架的发展，并行计算技术逐渐成熟，已经能够有效解决计算瓶颈，为海量大数据挖掘提供技术支持。从社会网络方面研究入手，社会网络的研究关键在于节点间的关系与社会属性。现实表明，真实的社会网络都呈现具有社区结构的特性，社区发现就是通过网络中节点间的连接关系挖掘社区结

5、构的过程。Louvain算法是一种基于模块度优化的高效算法，除了时间上的优势，还能探测到层次的社区结构，不会遗漏一些小型的社区。在研究Louvain算法的基础上，针对算法耗时问题，提出了并行化的改进思想进一步对算法效率进行优化，同时保证算法的精度不变。分布式计算框架的发展推动了分布式计算的应用，但是社区发现算法在分布式计算方面的应用却很少。面对具有海量数据的大规模复杂社交网络，利用分布式计算框架能进一步提高算法的运行效率，社区发现算法与分布式计算框架的结合必是社区发现未来的研究热点。Spark分布式计算框

6、架对社区发现算法这类需要大量迭代计算的算法有着很好的适应能力。将改进后的算法在Spark分布式平台上实现，进一步提高了运行效率。针对分布式计算中不同计算节点之间消息传递滞后产生的社区互换等问题，提出了连通图的方法加以改进。关键词：社区；Louvain算法；并行化；Spark；分布式计算-II-ABSTRACTResearchandImplementationofLouvainAlgorithminCommunityMiningABSTRACTWiththerapiddevelopmentofmodernn

7、etworktechnologysuchasInternetandcloudcomputing,weareenjoyingtheconveniencetheybringtoourlife.Peoplehavegraduallyenteredtheeraofbigdata,exponentiallyhugeamountsofdatanotonlybringchallengesandopportunitiesfortheemergingInternetenterprise,butalsoforthetradi

8、tionalindustry.ThecomplexityofthenetworknotonlyteststheexistingITinfrastructure,butalsochallengethecomputer'scalculationability.Intheageofthesocialnetworkingplatform,themajorsocialnetworkingsitesproduceterabytesofda