University of Illinois Urbana-Champaign

Speeding up stochastic block partitioning with graph coloring

Wang, Chih-Shin

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

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

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
Copyright and License Information
Copyright 2023 Chih-Shin Wang

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois