AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs
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 intu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9424548/ |
| _version_ | 1811274230943186944 |
|---|---|
| author | Sung-Soo Kim Young-Kuk Kim Young-Min Kang |
| author_facet | Sung-Soo Kim Young-Kuk Kim Young-Min Kang |
| author_sort | Sung-Soo Kim |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T23:15:18Z |
| format | Article |
| id | doaj.art-bc55c100d6124237bc7eef4779ba2f2a |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T23:15:18Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-bc55c100d6124237bc7eef4779ba2f2a2022-12-22T03:12:43ZengIEEEIEEE Access2169-35362021-01-019695396955810.1109/ACCESS.2021.30778889424548AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive GraphsSung-Soo Kim0https://orcid.org/0000-0003-3207-4648Young-Kuk Kim1Young-Min Kang2https://orcid.org/0000-0002-2796-194XArtificial Intelligence Research Laboratory, Electronics and Telecommunications Research Institute, Daejeon, South KoreaDepartment of Computer Science and Engineering, Chungnam National University, Daejeon, South KoreaDepartment of Game Engineering, Tongmyong University, Busan, South KoreaProcessing 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.https://ieeexplore.ieee.org/document/9424548/Reachability queryapproximate all-pairs shortest pathsgraph girthgraph embeddinghigher-order structural proximity |
| spellingShingle | Sung-Soo Kim Young-Kuk Kim Young-Min Kang AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs IEEE Access Reachability query approximate all-pairs shortest paths graph girth graph embedding higher-order structural proximity |
| title | AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs |
| title_full | AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs |
| title_fullStr | AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs |
| title_full_unstemmed | AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs |
| title_short | AORM: Fast Incremental Arbitrary-Order Reachability Matrix Computation for Massive Graphs |
| title_sort | aorm fast incremental arbitrary order reachability matrix computation for massive graphs |
| topic | Reachability query approximate all-pairs shortest paths graph girth graph embedding higher-order structural proximity |
| url | https://ieeexplore.ieee.org/document/9424548/ |
| work_keys_str_mv | AT sungsookim aormfastincrementalarbitraryorderreachabilitymatrixcomputationformassivegraphs AT youngkukkim aormfastincrementalarbitraryorderreachabilitymatrixcomputationformassivegraphs AT youngminkang aormfastincrementalarbitraryorderreachabilitymatrixcomputationformassivegraphs |