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

发布时间：2018-04-08 22:30

本文选题：PowerGraph　切入点：社会网络　出处：《河北师范大学》2017年硕士论文

【摘要】：图是一种基本的数据结构,能够体现出不同实体之间的关系。在不同的应用领域中,图被广泛用来表示十分复杂的数据,比如:社会网络、蛋白质网络、运输网络、书目网络以及更多其他网络。如今,个人、社区、组织、国家等行动者之间的关系越来越紧密,这些关系中所蕴含的有价值的信息也随之飞速增长,使得社会网络分析的研究日趋火热。一般而言,社会网络分析是一种重要的大数据发现技术。当前,拥有百万、甚至亿万节点和边的大规模社会网络已十分普遍,为了处理和分析大规模网络出现了一些符合其计算特点的分布式图并行计算平台。然而,由于许多社会网络分析的经典算法都是基于单机设计的集中式算法,无法满足大规模社会网络分析的需求。因此,本文着重从社会网络传播、矩阵分解、网络重构这三方面入手,在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)。通过实验对算法的可行性与可扩展性进行了分析。
[Abstract]:A graph is a basic data structure that can reflect the relationships between different entities.In a variety of applications, graphs are widely used to represent very complex data, such as social networks, protein networks, transport networks, bibliographic networks, and more.Nowadays, the relationship among individual, community, organization, state and other actors is getting closer and closer. The valuable information contained in these relationships is also increasing rapidly, which makes the research of social network analysis become more and more hot.Generally speaking, social network analysis is an important big data discovery technology.At present, large-scale social networks with millions, even billions of nodes and edges are very common. In order to deal with and analyze large-scale networks, there are some distributed graph parallel computing platforms which accord with its computing characteristics.However, because many classical algorithms of social network analysis are centralized algorithms based on single computer, they can not meet the needs of large-scale social network analysis.Therefore, this paper focuses on the three aspects of social network propagation, matrix decomposition and network reconstruction, and designs and implements the parallel graph data analysis algorithm under the PowerGraph graph parallel computing framework.The main work of this paper is as follows: 1) the spread of virus and information in parallel communication algorithm based on PowerGraph can be regarded as the behavior of spreading from a certain law.Through the communication model, we can imitate these communication behaviors and help people understand the communication mechanism.There are many kinds of transmission models, and the transmission models are different for different viruses or information. The classical transmission models are SISSIRS / SIRS / SEIRs.Based on PowerGraph, a parallel propagation algorithm for SEIR model, PSA-SEIR(Parallel Spreading Algorithm for SEIR Modeler, is proposed in this paper.Experimental results show that the simulation results are consistent with the propagation trend of the SEIR model. At the same time, the extensibility of the algorithm is analyzed. 2) the parallel matrix decomposition algorithm based on PowerGraph is a common method in social network analysis.Because many networks can be abstracted as matrices, the algorithm of social network analysis can be realized by matrix calculation.Therefore, understanding and implementing the decomposition of large sparse matrices can solve many practical problems (such as: film recommendation).Based on this, the parallel SVD algorithm is improved, and the LRA-PSVD Rate Adjustment Parallel SVD algorithm with adjustable learning rate is proposed based on PowerGraph.Experimental results show that LRA-PSVD improves the accuracy of the algorithm. In addition, it is proved that the algorithm is extensible. 3) the topological structure of parallel reconstruction algorithm network based on PowerGraph is closely related to its many basic characteristics.Homogeneity is an important feature of network macro topology, and the change of homogeneity means the change of network topology.Through network reconstruction, a network with different matching coefficients is constructed, which is helpful to analyze the influence of homogeneity on other features of the network, such as propagation characteristics and robustness.Based on this, a parallel random reconstruction algorithm based on PowerGraph, PRRWA(Parallel Random Rewiring algorithm, is proposed to enhance the network homogeneity under the condition of invariant degree sequence.The feasibility and expansibility of the algorithm are analyzed through experiments.
【学位授予单位】：河北师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP311.13

【相似文献】