상세정보
학술지
AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs
- 발행일
- 202105
- 출처
- IEEE Access, v.9, pp.69539-69558
- ISSN
- 2169-3536
- 출판사
- IEEE
- 협약과제
- 21HS2100, 클라우드 엣지 기반 도시교통 브레인 핵심기술 개발, 정문영
- 초록
- Processing a reachability query in large-scale networks using existing methods remains one of the most challenging problems in graph mining. In this paper, we propose a novel incremental algorithmic framework for arbitrary-order reachability computation in massive graphs. The proposed method is intuitive and significantly outperforms the currently known methods in terms of computation time. We focus on the arbitrary-order reachability matrix framework called AORM, which can handle directed and disconnected networks such as citation networks. The AORM can handle diverse types of real-world datasets.We conduct extensive experimental studies with twenty synthetic networks generated from five random graph generation models and twenty massive real-world networks. The experimental results show the advantages of the method in terms of both computational efficiency and approximation controllability. In particular, the proposed method outperforms up to 10 times compared to NetworkX for incremental all-pairs shortest paths computation. Moreover, the computational results of the method rapidly converge to the ground truths. Thus, we can get the correct solution in the early stage of the incremental approximation. We can employ the method as a versatile feature extraction framework for network embedding. Overall, the experimental results present a remarkable improvement in speed-up for reachability computation.
- KSP 제안 키워드
- All-pairs shortest paths, Citation Network, Computational Efficiency, Experimental study, Feature extraction framework, Graph mining, Large-scale network, Massive graphs, Network Embedding, Random graph generation, Reachability matrix
본 저작물은 크리에이티브 커먼즈 저작자 표시 (CC BY) 조건에 따라 이용할 수 있습니다.
