ALGEBRAIC METHODS ON STATIC AND STREAMING GRAPHS
| Autor: | Tumurbaatar, Altansuren |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Eigenvector centrality
percolation centrality reachability in streaming graphs temporal foremost path Katz centrality Brandes��� algorithm algebraic graph algorithm scalability algebraic graph algorithms graph centralities on streaming graphs betweenness centrality MathematicsofComputing_DISCRETEMATHEMATICS semiring of endomorphisms Dijksra���s algorithm |
| DOI: | 10.7273/000002451 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|