{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120434"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120434","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Speeding up stochastic block partitioning with graph coloring","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-05-01","abstract_has_math":false,"creators":["Wang, Chih-Shin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:57Z","subjects":["Graphchallenge","Stochastic Block Partitioning","Vertex Coloring","Parallel Algorithms","Partitioning Algorithms"],"languages":["en","eng"],"rights":["Copyright 2023 Chih-Shin Wang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120434","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Wang, Chih-Shin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-05-02"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graphchallenge","Stochastic Block Partitioning","Vertex Coloring","Parallel Algorithms","Partitioning Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Chih-Shin Wang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120434"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Speeding up stochastic block partitioning with graph coloring"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F."],"dc:creator":["Wang, Chih-Shin"],"dc:date":["2023-05","2023-05-02"],"dc:description":["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","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120434"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Chih-Shin Wang"],"dc:subject":["Graphchallenge","Stochastic Block Partitioning","Vertex Coloring","Parallel Algorithms","Partitioning Algorithms"],"dc:title":["Speeding up stochastic block partitioning with graph coloring"],"dc:type":["text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}