Speeding up stochastic block partitioning with graph coloring

Graph partition is a well-known NP-hard problem. It is widely used in various applications regarding realworld scenario graphs. Various approaches have been developed to deal with the problem. One renowned approach used within the IEEE HPEC Graph Challenge is the Bayesian statistics-based stochastic block partitioning (SBP) [1]. This method yields high-quality partitions in sub-quadratic time; however, it does not scale well in large graphs. In this thesis, we aim to parallelize the algorithm in order to improve its runtime performance. We first present various attempts that failed to speed up the algorithm. Then, we present the graph coloring approach that helps to speed up the baseline SBP algorithm provided in the Graph Challenge. With 16 virtual CPUs, we achieved 1.5–3.87x speedup for static graphs with size between 500 and 20000 nodes. With snapshot technique and graph coloring, we achieved 4.5–33.8x speedup in streaming graphs with total graph size 500 to 20000.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Wang, Chih-Shin

Contributors dc:contributor

• Wong, Martin D.F.

• Graphchallenge
• Stochastic Block Partitioning
• Vertex Coloring
• Parallel Algorithms
• Partitioning Algorithms

Statement dc:rights

• Copyright 2023 Chih-Shin Wang

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120434

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120434