Master Thesis MSTR-2019-60

BibliographyGeppert, Heiko: Massive hypergraph partitioning.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 60 (2019).
76 pages, english.
Abstract

The hypergraph model is a more generic version of the graph model. Instead of edges connecting only two vertices, hyperedges can connect an arbitrary number of vertices. This way, the hypergraph model has a higher expressiveness than the original graph model. It can model group memberships in social media or group chats in messengers easily. In the past years both, social media and instant messengers, gained much more popularity. The increased number of users and the thus increasing traffic result in larger hypergraph data sets, which can not be processed by a single machine. Hence, the hypergraphs need to be partitioned, thereby maintaining a low communication overhead in the later processing and having balanced partition sizes to ensure efficient parallelization. There are already many hypergraph partitioning algorithms so far, yet they are often limited in their parallelization, which is needed to process massive hypergraphs. A known paradigm which can be parallelized easily is label propagation. We created three approaches called Credit Label Propagation (CLP), Split Credit Label Propagation (SCLP) and Split Credit Label Propagation -- Credit Value Compensation (SCLP-cc) based on label propagation introducing new balancing punishments to improve the partitions balance leading to a better scalability. Thereby we introduced a credit value to regulate the growth of the label clusters. In the later algorithms we modified the credit value handling to prevent clusters from becoming to large, by regulating the amount of credit value available in the system. Further, we created a novel hypergraph partitioning algorithm called Gravity Expansion based on graph visualization algorithms. The hypergraphs vertices are placed in the center of a two-dimensional space. Next they are expanded into the space while keeping connected vertices close due to vertex movements via barrier jumps. After the expansion two gravity holes are placed which absorb and therefore partition the vertices. During the absorbing the vertices are further expanded to react to previous assignments. The SCLP-cc algorithm outperformed the Label Propagation Partitioning algorithm from the hyperX framework in terms of balance and cut size. Our Gravity Expansion algorithm outperformed hMetis when creating many subgraphs. In addition, it outperformed the publicly available version of Hype in terms of the cut size on some input graphs. Summarized, we provide new approaches for label propagation partitioning algorithms to increase the balancing. Further, we created a novel scalable partitioning algorithm which introduces the field of visualization algorithms to the partitioning problem.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Bhowmik, Dr. Sukanya
Entry dateDecember 18, 2019
   Publ. Computer Science