Hadoop平台下AP聚类社团检测算法的并行化

发布时间：2020-02-02 05:48

【摘要】：复杂网络作为生活中电力系统、通信网络和万维网等复杂系统的高度抽象,复杂网络社团结构表示着网络中的节点聚合的趋势,是复杂网络的一个重要的拓扑属性。社团检测可以有效认识复杂网络的结构和功能,进而对网络中的行为模式进行预测和分析,对复杂系统的研究与应用具有重要的意义。现有的大多数复杂网络社团检测算法都在追求算法的准确度,而忽略了时间复杂度高的问题。本文针对目前社团检测算法在处理大规模数据时在速率上不足的问题,设计了一种在Hadoop平台下进行的社团检测的并行化方法。本文主要工作如下:1.本文对复杂网络的基础知识和现有社团检测算法进行了研究。简述了复杂网络基本理论,介绍了社团检测算法的研究现状,重点介绍了几种流行的社团检测算法的基本思想和计算过程。2.由于可以通过相似度将复杂网络的社团检测问题转化为相似节点的聚类问题,本文对AP聚类(Affinity Propagation Clustering)进行了深入的研究,针对传统AP聚类在计算相似度时用欧氏距离而没有考虑到复杂网络的集聚特性的问题,本文采用一种改进的Jaccard系数来计算复杂网络节点之间的相似度。3.针对社团检测AP聚类在处理大规模数据速度慢的问题,结合大数据分析工具Hadoop,设计一种分步并行化的AP聚类社团检测方法,将AP算法整个过程分步进行并行化来实现社团检测的AP聚类算法的并行化。在PC机上搭建Hadoop集群,在不同规模的数据集上对本文设计的计算方法进行测试。实验中分别对本文设计的方法在算法准确度和方法性能上进行的测试,结果表明,本文方法在进行社团检测时具有良好的准确度和计算性能,尤其是在大规模数据集中,本文方法能够取得较好的加速比。
【图文】：

本概念出发介绍复杂网络的基础知识，简单络特性和提出的各种网络模型。然后从社团的社团检测算法，，最后简介了本文算法的中，个体总是和周围的环境紧密联系的，从，网络里的元素相互结合、相互依赖、相互络，本节将在多个角度上介绍复杂网络。概念表包含大量元素以及元素之间相互作用的相互作用视作网络中节点与节点之间的连接如图 2-1 就表示一个拥有 10 个元素和它们

简单无权图
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13;O157.5

【参考文献】

相关期刊论文 前10条

1 孙贵宾;周勇;;基于结构相似度仿射传播的社团检测算法[J];计算机应用;2015年03期

2 唐艳琴;潘志松;吴君青;;基于MapReduce的快速Newman并行算法[J];华中科技大学学报(自然科学版);2012年S1期

3 李国杰;程学旗;;大数据研究:未来科技及经济社会发展的重大战略领域——大数据的研究现状与科学思考[J];中国科学院院刊;2012年06期

4 鲁伟明;杜晨阳;魏宝刚;沈春辉;叶振超;;基于MapReduce的分布式近邻传播聚类算法[J];计算机研究与发展;2012年08期

5 姜雅文;贾彩燕;于剑;;基于节点相似度的网络社团检测算法研究[J];计算机科学;2011年07期

6 骆志刚;丁凡;蒋晓舟;石金龙;;复杂网络社团发现算法研究新进展[J];国防科技大学学报;2011年01期

7 周世兵;徐振源;唐旭清;;基于近邻传播算法的最佳聚类数确定方法比较研究[J];计算机科学;2011年02期

8 赵宪佳;王立宏;;近邻传播半监督聚类算法的分析与改进[J];计算机工程与应用;2010年36期

9 董俊;王锁萍;熊范纶;;可变相似性度量的近邻传播聚类[J];电子与信息学报;2010年03期

10 杨博;刘大有;金弟;马海宾;;复杂网络聚类方法[J];软件学报;2009年01期

相关硕士学位论文 前7条

1 金才园;基于Hadoop平台的角色挖掘算法研究[D];东南大学;2016年

2 陈奔燕;复杂网络的社团探测[D];湘潭大学;2015年

3 吴蔚蔚;基于相似度的复杂网络社团发现算法研究[D];上海交通大学;2015年

4 李金朋;基于Hadoop平台的重叠社区发现算法研究[D];吉林大学;2014年

5 李尚英;社团划分算法并行化研究[D];山东师范大学;2012年

6 李争光;复杂网络中的社团发现算法研究[D];上海交通大学;2012年

7 温程;并行聚类算法在MapReduce上的实现[D];浙江大学;2011年

本文编号：2575626