Fast Computation of All-pairs Random Walk on Large Graphs
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.