基于协同边推导的动态流式图并行抽样算法

发布时间：2018-05-05 08:23

本文选题：动态图 + 流式图　；参考：《华中科技大学》2016年硕士论文

【摘要】：随着应用不断深入,在社交网络服务、科学计算仿真等场景中,图数据持续、大量产生,对其进行快速、有效分析具有十分重要的意义。在某些对精确度要求不是很高或者只要求反映部分关键图特性的应用中,采取从原图中抽取具有代表性的子图进行分析的方法,能节省计算资源和提高处理效率。对动态图抽样时,原图的持续变化导致抽样过程中无法获取全图静态数据,故通常采用流式的抽样算法。不过流式抽样算法由于累计迭代特性,抽样过程必须串行,因此当抽样子图规模较大时,抽样过程减速严重,难以保证实时性,而若抽样子图偏小,则难以保证其与原图相似。现有并行抽样算法针对的都是静态图,不适用于动态图,因此需要提出一种并行的流式抽样算法。研究分析典型的流式图抽样算法PIES(Partial-Induce Edge Sampling)及其改进算法PIES-INV,分析PIES并行化方案存在的问题,提出了一种基于协同边推导的动态流式图并行抽样算法PaStS(Parallel Streaming Sampling)。PaStS与PIES-INV采取相同的暂存点替换策略,在并行抽样时,利用全局点信息同步的机制实现动态调整各抽样器的抽样目标大小,以及实现基于全局点集的协同边推导,从而解决流式抽样算法并行化时点和边大量减少的问题。经过在真实动态图数据集和生成图数据集上的测试,PaStS算法相比PIES,在并行度为8时抽样效率能提高15到49倍。PaStS抽样得到的子图在四种图特性的代表性上与PIES-INV比较接近,在多数情况下都比PIES好。但是在度分布较为均匀的图中,PaStS算法在度分布特性和k-core分布特性上不如PIES。另外,PaStS算法在不同数据集上的集聚系数特性上表现比PIES和PIES-INV稳定,在有效直径特性上表现比PIES稳定。图数据快速变化时PaStS仍能保持较好的抽样效果及稳定性。
[Abstract]:With the deepening of applications, in the social network services, scientific computing simulation and other scenarios, graph data continue to be generated in large quantities, it is of great significance to analyze them quickly and effectively. In some applications where the accuracy requirement is not very high or only some key graph characteristics are required to be reflected, the method of extracting representative subgraphs from the original image for analysis can save computing resources and improve processing efficiency. When sampling the dynamic graph, the continuous change of the original map makes it impossible to obtain the static data of the whole graph during the sampling process, so the flow sampling algorithm is usually used. However, because of the accumulative iterative characteristic, the sampling process must be serialized, so the sampling process decelerates seriously when the drawing scale is large, and it is difficult to guarantee the real-time performance of the sampling process, but it is difficult to ensure that the sampling process is similar to the original one if the drawing image is small. The existing parallel sampling algorithms are all static graphs, which are not suitable for dynamic graphs, so we need to propose a parallel flow sampling algorithm. This paper studies and analyzes the typical flow diagram sampling algorithm PIES(Partial-Induce Edge sampling and its improved algorithm PIES-INV, and analyzes the problems of PIES parallelization scheme. In this paper, a parallel sampling algorithm for dynamic flow diagram based on co-edge derivation is proposed. PaStS(Parallel Streaming Sampling).PaStS and PIES-INV adopt the same temporary point replacement strategy. The mechanism of global point information synchronization is used to dynamically adjust the sampling target size of each sampler and to realize the cooperative-edge derivation based on the global point set, thus solving the problem of parallelizing the time points and reducing the edge of the flow sampling algorithm. After testing on real dynamic graph data set and generating graph data set, compared with Piesi, the efficiency of sampling with parallel degree of 8 can be improved by 15 to 49 times. PaStS is similar to PIES-INV in the representativeness of four kinds of graph characteristics. In most cases it is better than PIES. However, in the graph with uniform degree distribution, PaStS algorithm is inferior to Piesi in degree distribution and k-core distribution. In addition, PaStS algorithm is more stable than PIES and PIES-INV in the characteristic of aggregation coefficient on different data sets, and more stable than PIES in the characteristic of effective diameter. PaStS can still maintain good sampling effect and stability when the map data changes rapidly.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP391.41

【相似文献】