基于Pregel-Like架构的并行图挖掘平台研究与实现

发布时间：2019-03-02 10:07

【摘要】：图作为非结构化数据中的一种重要的类型,比线性表和树结构在语义和结构方面都有更强的表示能力。很多现实世界中的问题都可以用图来表示,对图数据的处理以及相关的应用无处不在。而随着信息爆炸型增长及社会网络的大力发展,需要处理的图数据的规模与日俱增,这对大规模图的高效处理提出了巨大挑战。云计算是处理海量数据挖掘任务、提升海量数据挖掘能力的有效手段之一,本文正是以这个思路为出发点,设计并实现了一个基于Pregel-Like架构的并行图挖掘平台。底层云存储架构选择HDFS(Hadoop Distributed File System),可以为大规模图的存储提供高效、安全、高容错的支持。云计算框架使用BSP(Bulk Synchronous Parallel model)模型,其特有的超级步非常适合需要迭代计算的图算法,使得对大规模图数据的分析成为可能。平台集成了各类图挖掘算法,并对各算法分析结果及网络拓扑结构提供了可视化展示。本文的主要工作是通过对经典图挖掘算法及相关改进算法的调研,在底层框架的基础上设计并实现了图属性分析和图排序中对经典重要算法的改进算法,并结合实际数据集对经典算法及改进算法的结果做了对比,最后提出了一种新的图聚类算法。具体内容如下:1)设计并实现了 K-shell分解和半局部中心性两种图属性并行算法,两者相比于度值可以更好地刻画节点重要性,计算复杂度又要比介数的计算低,基于公共数据集分析了两者的分布及与度的相关分布。2)设计并实现了 LeaderRank 和 SALSA(Stochastic Approach for Link Structure Analysis)两种图排序算法,前者相比于PageRank算法收敛更快,能够更好地识别有影响力的节点,且抗干扰能力强。后者相比于 HITS(Hypertext-Induced Topic Search)算法,其 hub 值能更好地衡量节点传播能力。3)提出了一种基于K-shell值的社团发现算法,通过K-shell分解缩小网络规模提高运行效率,根据“基准”网络验证了正确性。
[Abstract]:As an important type of unstructured data, graphs have better semantic and structural representation than linear tables and tree structures. Many real-world problems can be represented by graphs, and the processing of graph data and related applications are everywhere. With the explosive growth of information and the vigorous development of social network, the scale of graph data that needs to be processed is increasing day by day, which poses a great challenge to the efficient processing of large-scale graph. Cloud computing is one of the effective means to deal with the task of massive data mining and to improve the capability of massive data mining. This paper designs and implements a parallel graph mining platform based on Pregel-Like architecture with this idea as the starting point. The underlying cloud storage architecture, HDFS (Hadoop Distributed File System), can provide efficient, secure, and fault-tolerant support for large-scale graph storage. Cloud computing framework uses BSP (Bulk Synchronous Parallel model) model, and its unique super-step is very suitable for graph algorithm which needs iterative computation, which makes it possible to analyze large-scale graph data. The platform integrates all kinds of graph mining algorithms, and provides a visual display of the analysis results and network topology of each algorithm. The main work of this paper is to design and implement an improved algorithm of classical important algorithm in graph attribute analysis and graph sorting based on the investigation of classical graph mining algorithm and related improved algorithm. The results of the classical algorithm and the improved algorithm are compared with the actual data set. Finally, a new graph clustering algorithm is proposed. The main contents are as follows: 1) the parallel algorithms of K-shell decomposition and semi-local centrality are designed and implemented. Compared with the values, the two algorithms can better describe the importance of nodes, and the computational complexity is lower than that of the meshwork. Based on the common data set, we analyze the distribution of the two and the correlation distribution of degree. 2) We design and implement two kinds of graph sorting algorithms: LeaderRank and SALSA (Stochastic Approach for Link Structure Analysis), the former converges faster than the PageRank algorithm, and the former converges faster than the PageRank algorithm. Can better identify influential nodes, and strong anti-interference ability. Compared with HITS (Hypertext-Induced Topic Search), the hub value of the latter can better measure the propagation ability of nodes. 3) A community discovery algorithm based on K-shell value is proposed, which reduces the size of the network and improves the efficiency of operation by K-shell decomposition. The correctness is verified according to the "benchmark" network.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13

【相似文献】