Files and links (1)
CC BY-NC-ND V4.0, Open Access
Dissertation
Structure Detection in Graphs and Hypergraphs
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2021
DOI:
https://doi.org/10.7273/000002440
Handle:
https://hdl.handle.net/2376/119098
Abstract
Understanding relationships among entities in large-scale systems is a fundamental operation in data science. Such systems can be modeled as graphs if the relationships are pairwise or as hypergraphs if the relationships are multi-way. Structures in graphs and hypergraphs such as communities or connected components and metrics such as centrality indices encapsulate relationships among entities. For community detection and connected components decomposition, in graphs and hypergraphs, as the sizes of the systems continue to increase, we generally need fast algorithms to enable large-scale real-time processing. The first goal of this thesis is to develop linear-time algorithms that can be used to detect communities and connected components in graphs. We achieve this by developing a new framework based on Direction-optimizing Label Propagation Algorithm (DOLPA). We parallelize DOLPA in both shared-memory and distributed-memory. Since community detection is NP-hard, it is difficult for community detection algorithms to achieve both high quality of solution and fast convergence at the same time. As the second goal of this thesis, DOLPA provides a trade-off to accommodate different community detection scenarios: accurate detection versus fast detection.
The other two goals of the thesis target hypergraphs. Hypergraphs are increasingly becoming important in data science applications due to their capability for robust data representation. However, their computational complexity can be high. To reduce this complexity, lower-dimensional approximations of hypergraphs to compute relevant structures are needed. Line graphs, in particular, high order s-line graphs for s > 1 of hypergraphs are a critical tool for this purpose, since they capture important hypergraph properties. Obtaining high order s-line graphs is highly compute-intensive and irregular. Until recently, no efficient algorithm has been proposed to compute s-line graphs for s>=2. The third goal of this thesis is to develop a scalable framework for s-line graph computation and s-metrics computation for arbitrary s values. The framework is applied for hypergraph structure detection in real-world systems. The last goal of the thesis is to design algorithms to speedup s-line graph computation. The new algorithms are orders of magnitude faster than a naive algorithm and the SpGEMM algorithm with filtration.
Metrics
22 File views/ downloads
106 Record Views
Details
- Title
- Structure Detection in Graphs and Hypergraphs
- Creators
- Xu Tony Liu
- Contributors
- Assefaw Gebremedhin (Advisor)Andrew Lumsdaine (Advisor)Mahantesh Halappanavar (Committee Member)Anantharaman Kalyanaraman (Committee Member)Yinghui Wu (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 219
- Identifiers
- 99900606854501842
- Language
- English
- Resource Type
- Dissertation