大规模网络分析的中心性算法并行化研究

发布时间：2017-05-12 22:05

  本文关键词：大规模网络分析的中心性算法并行化研究，，由笔耕文化传播整理发布。

【摘要】：随着近十几年互联网的飞速发展,用户数量的迅速增加使得海量的用户数据被不断地制造出来,往往都是几百万甚至上千万的超大规模数据集。因此,如何从如此海量的用户数据中筛选出有用信息,从而进一步挖掘其深层的商业价值、理解其内在的商业行为以及发现隐含的新的业务增长点成为一个重要的研究方向和挑战。但是互联网的不断深化导致了用户数据规模的迅速增加,从而给社会网络分析算法和工具带来了新的要求和挑战,即大规模网络数据分析能力。本文旨在解决单机多核的系统平台下的大规模网络数据分析处理。中心性分析是网络分析研究中的重点,它主要描述了网络中的节点(个人或者组织)在网络中具有怎样的权力,居于怎样的中心地位,对于信息在整个网络中如何传播以及对传播有怎样的控制效果。随着计算机硬件技术的摩尔式飞速发展,以及并行技术和并行算法的日益成熟,我们选择中心性算法的并行化来解决基于单机多核的大规模网络数据分析问题。以下是本文的主要研究成果:1.本文受到复杂网络小世界的特性的启发,结合算法并行化分而治之的原则,分别对度中心性、临近中心性算法进行并行化设计,尤其在介数中心性算法中,把图遍历(BFS)的过程当做独立的运行模块,并把处理器分配给它们,实现并行化运算,提出介数中心性算法的粗粒度和细粒度并行算法。2.本文充分考虑真实世界网络的非平衡度分布的特性,去除真实世界网络中大量度为1的顶点,并修改并行算法代码,改进优化算法。3.本文选择matlab的并行工具箱,采用parfor数据并行编程模块,进行单机多核算法并行化实现。4.最后,基于单机多核的系统环境和MATLAB工具平台,分别采用并行算法和非并行算法对不同规模的实验数据进行中心性分析以验证算法并行化的性能和运行效果。接下来使用结束中心性并行算法对酵母蛋白质交互网络进行分析和关联挖掘:度中心性较高的蛋白质有很大的几率拥有高介数中心性值。
【关键词】：复杂网络 大规模网络分析 中心性分析 算法并行化
【学位授予单位】：云南财经大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02
【目录】：

• 摘要3-4
• Abstract4-9
• 第一章 绪论9-19
• 第一节 研究背景和意义9-12
• 一、背景和意义9-11
• 二、提出问题11-12
• 第二节 国内外研究动态12-15
• 第三节 算法并行化必要性分析15-16
• 第四节 本文的主要工作和研究思路16-18
• 第五节 本文的组织结构18-19
• 第二章 相关理论和方法19-31
• 第一节 复杂网络的基本特性19-22
• 一、小世界网络19-21
• 二、度分布21-22
• 三、中心性22
• 第二节 相关图论知识22
• 第三节 中心性度量方法22-27
• 一、度中心性（degree centrality）23
• 二、临近中心性（closeness centrality）23-24
• 三、压力中心性（stress centrality）24-25
• 四、介数中心性（betweeness centrality）25-26
• 五、特征向量中心性(Eigenvector Centrality)26
• 六、其他中心性方法26-27
• 第四节 并行计算与算法并行设计27-28
• 第五节 网络拓扑优化28-30
• 第六节 本章小结30-31
• 第三章 中心性算法并行化设计31-41
• 第一节 度中心性31
• 第二节临近中心性31-33
• 第三节 介数中心性33-39
• 一、介数中心性算法33-37
• 二、介数中心性算法并行设计37-39
• 第四节 本章小结39-41
• 第四章 算法优化和并行化实现41-47
• 第一节 算法优化41-43
• 一、算法优化设计思想41-42
• 二、算法优化代码42-43
• 第二节 算法并行化具体实现43-46
• 一、MATLAB并行原理43
• 二、初始化matlab并行环境43-44
• 三、在MATLAB中编写并行代码44-46
• 第三节 本章小结46-47
• 第五章 实验分析47-55
• 第一节 实验准备工作47
• 第二节 实验数据47-49
• 一、人工合成图47
• 二、真实世界中的网络47-49
• 第三节 实验分析49-54
• 一、小型数据集实验效果（人工合成图）49-51
• 二、大规模数据集实验效果51-52
• 三、蛋白质交互网络52-54
• 第四节 本章小结54-55
• 第六章 总结与展望55-57
• 第一节 本文工作总结55-56
• 第二节 未来工作展望56-57
• 参考文献57-62
• 致谢62-64
• 本人在读期间完成的研究成果64

【相似文献】

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

1 宋彦民;;网络中心性指标在技术测度中的应用探讨[J];电子测试;2014年03期

2 李静茹;喻莉;赵佳;;加权社交网络节点中心性计算模型[J];电子科技大学学报;2014年03期

3 陈国强;陈亮;;一种基于资源分配策略的复杂网络中心性测度[J];计算机科学;2011年08期

4 王瑶莉;高松;刘瑜;;青岛城市道路邻近中心性及其应用方法[J];地理研究;2013年03期

5 李卓;;基于节点中心性的移动机会网络网关选择算法[J];北京信息科技大学学报(自然科学版);2014年03期

6 邵浩;陈东方;刘欣;;复杂网络算法中K-shell与介数中心性算法的实现[J];现代计算机(专业版);2014年17期

7 徐健;;基于复杂网络的节点影响力评价模型研究[J];软件导刊;2014年03期

8 周涛;;专栏评述[J];电子科技大学学报;2014年03期

9 施杨;李南;;研发团队知识交流网络中心性对知识扩散影响及其实证研究[J];情报理论与实践;2010年04期

10 刘欣;李鹏;刘t

本文编号：360940