基于AP算法的社区检测算法及其并行化研究

发布时间：2017-10-28 09:10

  本文关键词：基于AP算法的社区检测算法及其并行化研究

  更多相关文章： 社区检测 相似性 SSAP算法 Spark 并行化

【摘要】：现实生活中很多系统结构都能抽象成网络,比如关系网络、新陈代谢网络、电子邮件通信网络、移动电话网络等。这些网络能够根据内部的相互作用表现出某些结构特征,其中社区结构(Community Structure)是这类网络中一个重要的特征,对网络中的社区结构的进行检测的方法叫做社区检测(Community Detection)。社区检测作为网络分析的基本任务有助于其它网络计算任务的完成,近年来有很多针对社区检测的研究并取得了不少研究成果。科学技术的不断进步使得网络的规模不断增大,现有的部分社区检测算法已经不能胜任大规模网络的社区检测任务。另外,社区检测问题能够转化为聚类问题,所以本文主要从相似性算法、聚类算法和分布式并行化计算三个方面入手对社区检测问题进行研究,本文的主要内容如下:1.在现有的一些针对网络中顶点之间相似性进行计算的算法研究中,大多数算法要么时间复杂度过高,要么没有充分的考虑整个网络的拓扑结构。基于以上问题,本文以随机游走模型为基础并基于个性化排名算法APR(Approximate Page Rank)算法,提出了一种快速的相似性计算算法,使得该算法在充分考虑网络的拓扑情况下提高网络中顶点之间相似性计算的效率。2.在社区检测的聚类阶段,现有的一些聚类算法不能够充分的利用网络中所蕴含的信息使得检测出来的社区质量不高。基于以上问题,本文提出了一种适用于针对网络进行社区检测的半监督聚类算法SSAP(Similarity Set based Affinity Propagation),该算法是基于AP(Affinity Propagation)算法的一种改进,提高了聚类算法在迭代时的运行效率以及整个算法的收敛速度。并结合提出的相似性计算方法,把社区检测问题转化成为了聚类问题。3.随着分布式计算的技术越来越成熟,比如基于Hadoop平台的Map Reduce并行化计算框架、基于内存模型的并行化计算框架Spark等。这些分布式计算技术的出现使得先前不能在单机环境下完成的计算任务得以实现。同时,在社区检测任务中,由于面临的网络规模越来越庞大,至此,本文在Spark框架下对所提出的社区检测算法进行了并行化实现,利用分布式并行化的优势使得该算法能够对大规模的网络进行社区检测。
【关键词】：社区检测 相似性 SSAP算法 Spark 并行化
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13;TP393.06
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 绪论10-16
• 1.1 研究工作的背景与意义10-11
• 1.2 国内外研究现状11-14
• 1.3 本文的主要工作14
• 1.4 本论文的结构安排14-15
• 1.5 本章小结15-16
• 第二章 相关理论与技术16-27
• 2.1 网络简介16-17
• 2.2 网络的特征17-20
• 2.3 社区检测现有算法20-22
• 2.4 并行化计算框架22-26
• 2.4.1 内存计算框架Spark22-24
• 2.4.2 图计算模型Spark GraphX24-26
• 2.5 本章小结26-27
• 第三章 基于APR算法的相似性算法27-42
• 3.1 随机游走模型27-28
• 3.2 基于随机游走模型的APR算法28-35
• 3.2.1 相似性矩阵与相似性集合30-32
• 3.2.2 基于 APR 算法相似性算法32-35
• 3.3 相似性算法的并行化实现35-41
• 3.3.1 输入文件格式35-36
• 3.3.2 网络的初始化36-38
• 3.3.3 更新排名向量和剩余向量38-40
• 3.3.4 相似性的规范化及输出40-41
• 3.4 本章小结41-42
• 第四章 SSAP：一种基于AP算法的社区检测算法42-61
• 4.1 AP聚类算法42-45
• 4.1.1 算法的输入43-44
• 4.1.2 结果的划分44
• 4.1.3 算法的流程44-45
• 4.2 一种基于AP算法的社区检测算法45-52
• 4.2.1 因子图模型45-47
• 4.2.2 SSAP：基于相似性集合的AP聚类算法47-52
• 4.2.3 时间复杂度分析52
• 4.3 SSAP算法的并行化实现52-60
• 4.3.1 算法的输入及相似性网络图的初始化53-54
• 4.3.2 更新责任度54-56
• 4.3.3 更新可信度56-58
• 4.3.4 对社区进行划分58-60
• 4.4 本章小结60-61
• 第五章 实验及结果分析61-73
• 5.1 实验环境61-62
• 5.2 实验数据62-64
• 5.3 评价函数64-65
• 5.4 实验结果分析65-72
• 5.4.1 真实网络上的评价结果对比65-67
• 5.4.2 人工网络上的结果对评价比67-69
• 5.4.3 运行时间和迭代次数对比69-72
• 5.5 本章小结72-73
• 第六章 全文总结与展望73-75
• 6.1 本文总结73
• 6.2 未来的工作73-75
• 致谢75-76
• 参考文献76-82

【相似文献】

中国期刊全文数据库 前10条

1 吴正娟;职为梅;杨勇;范明;;并行化的粒子群技术[J];微计算机信息;2009年36期

2 齐书阳;;迎接并行化的明天[J];软件世界;2009年06期

3 曹琳,杨学军,金国华;两种并行化机制的分析[J];计算机研究与发展;1993年09期

4 金国华，，陈福接;并行化技术与工具[J];计算机研究与发展;1996年07期

5 蔡立志,童维勤,廖文昭;序列拼装程序的并行化研究与实现[J];计算机工程与应用;2003年14期

6 王伟;潘建伟;;有限差分法的并行化计算实现[J];电脑知识与技术;2008年07期

7 程锦松;;迭代法的并行化[J];安徽大学学报(自然科学版);1997年03期

8 陈再高;王s

本文编号：1107577