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