On the Parallelization of MCMC for Community Detection
On the Parallelization of MCMC for Community Detection
复制标题
论MCMC并行化社区检测
DOI：
10.1145/3545008.3545058
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Feng, Wu-chun
中科院分区：
文献类型：
--
作者：
Wanye, Frank;Gleyzer, Vitaliy;Kao, Edward;Feng, Wu-chun
现实世界的图数据集规模的快速增长需要为大型图设计并行和可扩展的图分析算法。社区检测是一种图形分析技术，在从生物信息学到网络安全的许多领域都有使用案例。用于执行社区检测的基于马尔可夫链蒙特卡罗（MCMC）的方法，例如随机块划分（SBP）算法，对于具有复杂结构的图是鲁棒的，但是由于底层MCMC算法的串行性质，传统上难以并行化。本文提出了混合SBP（H-SBP），一种新的混合方法并行化固有的顺序计算在每个MCMC链，SBP。H-SBP使用异步Gibbs串行处理一部分最有影响力的图顶点，并并行处理剩余的大多数顶点。我们的经验表明，H-SBP在保持准确性的同时，将MCMC计算速度提高了5.6倍。
The rapid growth in size of real-world graph datasets necessitates the design of parallel and scalable graph analytics algorithms for large graphs. Community detection is a graph analysis technique with use cases in many domains from bioinformatics to network security. Markov chain Monte Carlo (MCMC)-based methods for performing community detection, such as the stochastic block partitioning (SBP) algorithm, are robust to graphs with a complex structure, but have traditionally been difficult to parallelize due to the serial nature of the underlying MCMC algorithm. This paper presents hybrid SBP (H-SBP), a novel hybrid method to parallelize the inherently sequential computation within each MCMC chain, for SBP. H-SBP processes a fraction of the most influential graph vertices serially and the remaining majority of the vertices in parallel using asynchronous Gibbs. We empirically show that H-SBP speeds up the MCMC computations by up to 5.6 × on real-world graphs while maintaining accuracy.
FlexGibbs：用于结构化图的可重构并行 Gibbs 采样加速器
DOI：
--
发表时间：
2019
期刊：
IEEE Symposium on Field-Programmable Custom Computing Machines
影响因子：
--
作者：
Glenn G. Ko;Yuji Chai;Rob A. Rutenbar;D. Brooks;Gu
通讯作者：
Gu
使用 Vite 的可扩展分布式内存社区检测
DOI：
10.1109/hpec.2018.8547534
发表时间：
2018
期刊：
2018 IEEE High Performance extreme Computing Conference (HPEC
影响因子：
--
作者：
Ghosh, Sayan;Halappanavar, Mahantesh;Tumeo, Antonino;Kalyanaraman, Ananth;Gebremedhin, Assefaw H.
通讯作者：
Gebremedhin, Assefaw H.
使用志愿者计算网格寻找蛋白质结合位点
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Travis Desell;L. Newberg;M. Magdon;B. Szymański;W. Thompson
通讯作者：
W. Thompson