论文部分内容阅读
随着应用不断深入,在社交网络服务、科学计算仿真等场景中,图数据持续、大量产生,对其进行快速、有效分析具有十分重要的意义。在某些对精确度要求不是很高或者只要求反映部分关键图特性的应用中,采取从原图中抽取具有代表性的子图进行分析的方法,能节省计算资源和提高处理效率。对动态图抽样时,原图的持续变化导致抽样过程中无法获取全图静态数据,故通常采用流式的抽样算法。不过流式抽样算法由于累计迭代特性,抽样过程必须串行,因此当抽样子图规模较大时,抽样过程减速严重,难以保证实时性,而若抽样子图偏小,则难以保证其与原图相似。现有并行抽样算法针对的都是静态图,不适用于动态图,因此需要提出一种并行的流式抽样算法。研究分析典型的流式图抽样算法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仍能保持较好的抽样效果及稳定性。