基于PowerGraph并行计算框架的社会网络分析研究

摘要

图是一种基本的数据结构，能够体现出不同实体之间的关系。在不同的应用领域中，图被广泛用来表示十分复杂的数据，比如:社会网络、蛋白质网络、运输网络、书目网络以及更多其他网络。如今，个人、社区、组织、国家等行动者之间的关系越来越紧密，这些关系中所蕴含的有价值的信息也随之飞速增长，使得社会网络分析的研究日趋火热。一般而言，社会网络分析是一种重要的大数据发现技术。当前，拥有百万、甚至亿万节点和边的大规模社会网络已十分普遍，为了处理和分析大规模网络出现了一些符合其计算特点的分布式图并行计算平台。然而，由于许多社会网络分析的经典算法都是基于单机设计的集中式算法，无法满足大规模社会网络分析的需求。因此，本文着重从社会网络传播、矩阵分解、网络重构这三方面入手，在PowerGraph图并行计算框架下设计并实现并行图数据分析算法。本文主要完成了以下几个方面的工作:
　　1)基于PowerGraph的并行传播算法
　　病毒的蔓延、信息的扩散等，都可以看成是服从某种规律的网络传播行为。通过传播模型，可以模仿这些传播行为，有助于人们理解传播机制。传播模型有很多种，对不同的病毒或信息，适用的传播模型也不相同，经典的传播模型有SIS、SIR、SIRS、SEIR。本文基于PowerGraph提出面向SEIR模型的并行传播算法PSA-SEIR(ParallelSpreading Algorithm for SEIR Model)。经实验验证，仿真结果与SEIR模型的传播趋势相符，同时分析了算法的可扩展性。
　　2)基于PowerGraph的并行矩阵分解(SVD++）算法
　　在社会网络分析中，矩阵分解是常见的方法。由于许多网络都可以抽象为矩阵的形式，社会网络分析的算法可以以矩阵计算的方式实现。因此，了解并实现对大规模稀疏矩阵的分解，能够解决许多现实问题（如:电影推荐）。基于此，改进了并行SVD++算法，基于PowerGraph提出学习率可调的并行SVD++算法LRA-PSVD++(LearningRate Adjustment Parallel SVD++ Algorithm)。经实验验证，LRA-PSVD++提高了算法精度，此外，实验证明了算法具有可扩展性。
　　3)基于PowerGraph的并行重构算法
　　网络的拓扑结构与其许多基本特征有很大关系。同配性是网络宏观拓扑的一个重要特征，同配性的改变意味着网络拓扑结构的改变。通过网络重构，构造出具有不同同配系数的网络，有助于分析同配性对网络其他特征（如:传播特征、鲁棒性）的影响。基于此，以增强网络同配性为目标，在保持度序列不变的条件下提出了基于PowerGraph的并行随机重构算法PRRWA(Parallel Random Rewiring Algorithm)。通过实验对算法的可行性与可扩展性进行了分析。

目录

声明

摘要

1 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 传播动力学

1．2．2 矩阵分解

1．2．3 网络重构

1．3 论文主要工作与创新点

1．4 论文组织结构

2 图并行计算相关技术

2．1 图并行计算框架概述

2．2 并行编程模型

2．2．1 BSP编程模型

2．2．2 GAS编程模型

2．3 PowerGraph并行计算框架

2．3．1 软件栈

2．3．2 图划分策略

2．3．3 PowerGraph核心框架

2．4 本章小结

3 基于PowerGraph的并行传播算法

3．1 常见的传染病传播模型

3．1．1 SIS模型

3．1．2 SIR模型

3．1．3 SIRS模型

3．1．4 SEIR模型

3．2 PSA-SEIR算法设计

3．2．1 并行传播理论基础

3．2．2 数据结构

3．2．3 算法步骤

3．3 实验结果分析

3．3．1 实验环境及实验数据

3．3．2 实验结果与分析

3．4 本章小结

4 基于PowerGraph的并行矩阵分解算法

4．1 SVD++基本理论

4．2 基于学习率可调的SVD++理论

4．3 LRA-PSVD++算法设计

4．3．1 并行SVD++理论基础

4．3．2 数据结构

4．3．3 算法步骤

4．4 实验结果分析

4．4．1 实验环境及实验数据

4．4．2 算法质量度量指标

4．4．3 实验结果与分析

4．5 本章小结

5 基于PowerGraph的并行重构算法

5．1 增强网络同配性的随机重构基本理论

5．1．1 随机重构基本理论

5．1．2 增强网络同配性的随机重构理论

5．2 PRRWA算法设计

5．2．1 并行重构理论基础

5．2．2 数据结构

5．2．3 算法步骤

5．3 实验结果分析

5．3．1 实验环境及实验数据

5．3．2 实验结果与分析

5．4 本章小结

6 总结与展望

6．1 全文总结

6．2 后续工作展望

参考文献

致谢