一种重叠社区发现算法及其在MapReduce上的实现

《一种重叠社区发现算法及其在MapReduce上的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、代号10701学号1021121259分类号TP311.5密级公开题（中、英文）目一种重叠社区发现算法及其在MapReduce上的实现AnAlgorithmforOverlappingCommunityDetectionAndItsImplementationonMapReduce作者姓名葛军指导教师姓名、职务陈平教授学科门类工学学科、专业计算机软件与理论提交论文日期二○一三年一月创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子

2、科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在解密后遵守此规定)本

3、学位论文属于保密，在年解密后适用本授权书。本人签名：日期导师签名：日期摘要社区结构是复杂网络普遍存在的拓扑特性之一。挖掘网络中存在的社区结构成为近年来复杂网络领域中的热门问题，并取得了一定的研究成果。然而，随着网络的规模和结构日益复杂而庞大，现有的一些社区发现算法已不再适用。同时，复杂网络中可能存在着重叠结构，一些算法没有考虑到这一特点，以致无法发现网络中的重叠部分。为了解决上述问题，本文结合基于信号传播的相似度计算方法和模糊AP(AffinityPropagation)聚类，提出了一种新的可并行化的重叠社区发现算法CDSFAP(CommunityDetectionbySignal-

4、basedFuzzyAffinityPropagation)。首先，对基于信号传播的相似度计算方法进行了改进，提高了算法的计算准确性和处理复杂图结构的能力。接着，向模糊AP聚类中引入模糊熵(fuzzyentropy)理论，使得算法能够根据节点的模糊性，识别出网络图中的重叠节点。最后，借助MapReduce编程模式，将算法迁移到了云平台。通过对比CDSFAP算法与其它算法在多组测试集上的社区划分质量和运行效率，验证了算法的可行性。同时，在处理大规模网络测试集时，算法的MapReduce版本也表现出了较为理想的效果。关键词：社区发现重叠结构AP聚类MapReduceAbstractCom

5、munitystructureisoneofthecommontopologicalcharacteristicsincomplexnetworks.Communitydetectionhasbeenstudiedbyvariesofresearchersformanyyears.However,theproblemisstillnotsatisfactorilysolvedsincereal-worldnetworkstendtohaveaverycomplicatedstructureandextremelylargesize.Atthesametime,theoverlappi

6、ngpropertyofcommunities,whichexistscommoninmanyreal-worldnetworks,isoftenignored.Bycombiningsignal-basedsimilaritymeasureandfuzzyaffinitypropagation,wepresentanewcommunitydetectionalgorithmCDSFAP(CommunityDetectionbySignal-basedFuzzyAffinityPropagation)fortheproblemabove.Firstly,weimprovethesig

7、nal-basedsimilaritymethodintheaccuracyandpromoteitsabilitytosolvecomplicatedgraphstructure.Secondly,basedonfuzzyentropy,thealgorithmcanidentifyoverlappingnodesofcommunities.Finally,withthehelpofMapReduceprogrammingmodel,CDSFAPispo