On the Parallelization of MCMC for Community Detection
| dc.contributor.author | Wanye, Frank | en |
| dc.contributor.author | Gleyzer, Vitaliy | en |
| dc.contributor.author | Kao, Edward | en |
| dc.contributor.author | Feng, Wu-chun | en |
| dc.date.accessioned | 2023-02-10T17:59:59Z | en |
| dc.date.available | 2023-02-10T17:59:59Z | en |
| dc.date.issued | 2022-08-29 | en |
| dc.date.updated | 2023-01-23T15:13:28Z | en |
| dc.description.abstract | 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. | en |
| dc.description.version | Published version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.doi | https://doi.org/10.1145/3545008.3545058 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/113803 | en |
| dc.language.iso | en | en |
| dc.publisher | ACM | en |
| dc.rights | Creative Commons Attribution 4.0 International | en |
| dc.rights.holder | The author(s) | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | en |
| dc.title | On the Parallelization of MCMC for Community Detection | en |
| dc.type | Article - Refereed | en |
| dc.type.dcmitype | Text | en |