Fast Stochastic Block Partition for Streaming Graphs
Fast Stochastic Block Partition for Streaming Graphs
复制标题
流图的快速随机块划分
DOI：
10.1109/hpec.2018.8547523
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. H. Huang
中科院分区：
文献类型：
--
作者：
Ahsen J. Uppal;H. H. Huang
图划分问题仍然是具有挑战性的，特别是对于流图数据。虽然最优图划分是NP难的，但随机方法可以在合理的时间内提供近似解。然而，这样的方法是针对静态而不是动态图形数据优化的。在本文中，我们描述了一个新的高效的算法，我们已经开发的随机块划分时变，流图数据。我们的算法是IEEE HPEC图挑战赛[1]的基线算法的改进。我们的增量算法有效地更新其先前的内部状态，因为新的片段流入，并在每个时间步生成一个完整的分区。与在每个时间步从头开始执行完整分区的朴素基线相比，我们的算法提供了1.96 x（$\mathbf{N}=500$）和3.56 x（$\mathbf{N}= 20\mathbf {k}$）之间的加速比，对于10个部分的图形流，具有类似的准确性。在边际上，对于基线上的额外流片段的处理时间的加速在$\mathbf{N}=500$的7.1x到$\mathbf{N}=20\mathbf{k}$的25.1x之间。
The graph partition problem continues to be challenging, particularly for streaming graph data. Although optimal graph partitioning is NP-hard, stochastic methods can provide approximate solutions in reasonable time. However, such methods are optimized for static, not dynamic graph data. In this paper, we describe a new efficient algorithm we have developed for stochastic block partitioning on time-varying, streaming graph data. Our algorithm is a refinement of the baseline algorithm of the IEEE HPEC Graph Challenge [1]. Our incremental algorithm efficiently updates its previous internal state as new pieces are streamed in, and generates a complete partition at every time step. Compared to the naive baseline which performs a complete partitioning from scratch at every time step, our algorithm offers speedups between 1.96x for $\mathbf{N}=500$ and 3.56x for $\mathbf{N}=20\mathbf{k}$ overall, for a graph streamed over 10 parts, with similar accuracy. At the margin, the speedup in processing time for additional streaming pieces over the baseline is between 7.1x for $\mathbf{N}=500$ to 25.1x for $\mathbf{N}=20\mathbf{k}$.