Fast Computation of All-pairs Random Walk on Large Graphs

Information

Title Fast Computation of All-pairs Random Walk on Large Graphs
Authors Sungchan Park, Sang-goo Lee
Year 2012 / 7
Keywords Entity Search, RDF Graphs, Object Retrieval, Semantic Search, Structured Data, Semantic Web
Acknowledgement NRF
Publication Type International Conference
Publication Proceedings of the International Conference on Computer, Networks, Systems, and Industrial Applications 2012(CNSI 2012), pp. 1027-1028
Link url

Abstract

In this paper, we propose a novel strategy for fast computation of random walk probability for all node pairs on large graphs. Since computation of random walk includes a large number of random accesses to adjacency lists, it is time consuming task when whole graph cannot be loaded into main memory. We devise an efficient random walk computation algorithm for large graphs by reducing the number of random accesses to adjacency lists. We reduced the number of random accesses by reusing pre-computed results of other similar nodes. We also provide some discussions about related issues.