Overview
Bear is a novel method for fast, scalable, and accurate random-walk-with-restart (RWR) computation on large graphs.
Bear has two versions:
-
BearS is a preprocessing method for static graphs. BearS preprocesses a static graph in a fast and space-efficient way by reordering and partitioning the adjacency matrix of the graph. Then, BearS computes RWR scores quickly and accurately from the preprocessed matrices using block elimination.
-
BearD is an incremental update method for dynamic graphs.
BearD efficiently updates the changed parts in the preprocessed matrices.
Then, BearD computes RWR scores rapidly and exactly from the updated matrices.
Paper
BearS is described in the following paper:
-
BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs.
Kijung Shin, Jinhong Jung, Lee Sael, and U Kang.
ACM SIGMOD International Conference on Management of Data (SIGMOD) 2015, Melbourne, Australia
[PDF][BIBTEX]
BearD is described in the following paper:
-
Random Walk with Restart on Large Graph using Block Elimination.
Jinhong Jung, Kijung Shin, Lee Sael, and U Kang.
ACM Transactions on Database Systems (TODS) 2016, vol. 41, issue 2, pp. 12:1-12:43, June 2016
[PDF]
[BIBTEX]
Code
The binary codes used in the papers are available.
Datasets
People