BROWSE
Detail
Conference Paper
Sparsity-Aware Reachability Computation for Massive Graphs
Cited 2 time in 
Share 
Share
- Authors
- Sung-Soo Kim, Young-Min Kang, Young-Kuk Kim
- Issue Date
- 2022-01
- Citation
- International Conference on Big Data and Smart Computing (BigComp) 2022, pp.157-160
- Publisher
- IEEE
- Language
- English
- Type
- Conference Paper
- Abstract
- We propose a novel sparsity-aware reachability computation framework so-called S-AORM, which provides fast performance for massive graphs via incremental fashion using sparse matrices. S-AORM is straightforward to compre-hend and outperforms existing methods in terms of compu-tational performance. Five synthetic networks generated from Barab찼si-Albert model and five real-world networks are used in comprehensive experiments. In terms of all-pairs shortest paths computation performance on the citation network, which is a directed and disconnected network, the proposed approach surpasses SNAP by up to 12.1 times and NetworkX by up to 80.2 times. The overall experimental results demonstrate that our approach provides significant performance improvement in the graph reachability computation.
- KSP Keywords
- All-pairs shortest paths, Citation Network, Disconnected Network, Graph reachability, Massive graphs, Real-world networks, Sparse Matrices, computation performance, performance improvement, reachability computation