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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

第一节 研究背景和意义

第二节 国内外研究动态

第三节 算法并行化必要性分析

第四节 本文的主要工作和研究思路

第五节 本文的组织结构

第二章 相关理论和方法

第一节 复杂网络的基本特性

第二节 相关图论知识

第三节 中心性度量方法

第四节 并行计算与算法并行设计

第五节 网络拓扑优化

第六节 本章小结

第三章 中心性算法并行化设计

第一节 度中心性

第二节 临近中心性

第三节 介数中心性

第四节 本章小结

第四章 算法优化和并行化实现

第一节 算法优化

第二节 算法并行化具体实现

第三节 本章小结

第五章 实验分析

第一节 实验准备工作

第二节 实验数据

第三节 实验分析

第四节 本章小结

第六章 总结与展望

第一节 本文工作总结

第二节 未来工作展望

参考文献

致谢

本人在读期间完成的研究成果