Speeding up stochastic block partitioning with graph coloring

Wang, Chih-Shin

Permalink

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

Description

Title

Speeding up stochastic block partitioning with graph coloring

Author(s)

Wang, Chih-Shin

Issue Date

2023-05-02

Director of Research (if dissertation) or Advisor (if thesis)

Wong, Martin D.F.

Department of Study

Electrical and Computer Engineering

Discipline

Electrical and Computer Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• GraphChallenge
• stochastic block partitioning
• vertex coloring
• parallel algorithms
• partitioning algorithms

Abstract

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.

Graduation Semester

2023-05

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2023 Chih-Shin Wang

Owning Collections