2026-09-20T05:14:01Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/120434 2023-09-05 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Wong, Martin D.F. 2023-05 application/pdf en text Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-05-01 The student, Chih-Shin Wang, accepted the attached license on 2023-04-28 at 02:58. The student, Chih-Shin Wang, submitted this Thesis for approval on 2023-04-28 at 03:07. This Thesis was approved for publication on 2023-05-02 at 14:48. DSpace SAF Submission Ingestion Package generated from Vireo submission #19225 on 2023-09-01 at 17:15:16 Wang, Chih-Shin 2023-05-02 Graphchallenge Stochastic Block Partitioning Vertex Coloring Parallel Algorithms Partitioning Algorithms 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. Text eng https://hdl.handle.net/2142/120434 Copyright 2023 Chih-Shin Wang Speeding up stochastic block partitioning with graph coloring M.S. Thesis Electrical and Computer Engineering University of Illinois at Urbana-Champaign Electrical and Computer Engineering