상세정보
학술대회
Sparsity-Aware Reachability Computation for Massive Graphs
- 저자
- 김성수, 강영민, 김영국
- 발행일
- 202201
- 출처
- International Conference on Big Data and Smart Computing (BigComp) 2022, pp.157-160
- 협약과제
- 21HS2100, 클라우드 엣지 기반 도시교통 브레인 핵심기술 개발, 정문영
- 초록
- 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 제안 키워드
- All-pairs shortest paths, Citation Network, Disconnected Network, Graph reachability, Massive graphs, Real-world networks, Sparse Matrices, computation performance, performance improvement, reachability computation