Dissertation
ALGEBRAIC METHODS ON STATIC AND STREAMING GRAPHS
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2021
DOI:
https://doi.org/10.7273/000002451
Handle:
https://hdl.handle.net/2376/119687
Abstract
First, we explored different algebraic methods to write the betweenness centrality algorithm. Particularly, we focused on Brandes' algorithm [Brandes, 2001]. We aimed for Algebraic Betweenness Centrality (ABC) algorithms that can be parallelized easily. We proposed 3-tuple geodetic semiring as an extension to the usual geodetic semiring with 2-tuples [Batagelj, 1994]. Using the 3-tuple geodetic semiring, Dijkstra's and Brandes' algorithm, we wrote more concise and general ABC algorithm which is valid for weighted and directed graphs. We also proposed an alternative version of ABC using the usual geodetic semiring in which we used a simple way to construct shortest path tree after computing shortest path. This allows us to avoid computational complexity of ABC implementation using 3-tuple geodetic semiring. We used numba [Lam et al., 2015] to optimize and parallelize ABC. We evaluated the performance of ABC using 2-tuple geodetic semiring as compared to NetworkX [Hagberg et al., 2008], a common python package for graph algorithms. We did scalability experiments on parallel ABC and showed its total speedup. We also showed that with small modification, ABC can be adapted to algebraicly compute percolation centrality. Second, we explored algebraic methods on streaming graphs [Latapy et al., 2017]. We defined reachability intervals and Katz centrality in streaming graphs. We translated the shortest path problem with time constraints from [Gondran and Minoux, 2008], [Halpern and Priess, 1974] into finding reachability intervals in streaming graphs. We extended their method and proposed a semiring of endomorphisms for path counting which is used to compute reachability intervals along with path counts in streaming graphs. Based on this, we proposed an algebraic Katz centrality algorithm. We further use this semiring along with Brandes' and Dijkstra's algorithm to compute betweenness centrality in streaming graphs algebraicly. We also explored algebraic methods on streaming graphs without latency and wait time. We proposed an algebraic percolation centrality algorithm using the temporal geodetic semiring presented in [Batagelj and Praprotnik, 2015]. We presented an alternative definition of Katz centrality and eigenvector centrality based on reachability intervals rather than path counts and adjacency matrices of each time slices of a streaming graph respectively.
Metrics
29 File views/ downloads
103 Record Views
Details
- Title
- ALGEBRAIC METHODS ON STATIC AND STREAMING GRAPHS
- Creators
- Altansuren Tumurbaatar
- Contributors
- Matthew Sottile (Advisor)Kevin Vixie (Advisor)Michael Tsatsomeros (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Mathematics and Statistics, Department of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 136
- Identifiers
- 99900606855601842
- Language
- English
- Resource Type
- Dissertation