SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for computing SimRank, their computational costs are very high.

In this paper, we propose a framework for computing SimRank accurately. Our framework is based on the novel technique, linearized SimRank, which provides efficient algorithms for the single-pair, single-source, and all-pairs SimRank problems, respectively. More specifically, our framework consists of two phases, a preprocessing phase and a query phase. In the preprocessing phase, we estimate a parameter for a given graph and a desired accuracy by Monte Carlo simulation, and then in the query phase, we efficiently solve SimRank problems using this preprocessed parameter. Our algorithms are efficient in both time and space. The preprocessing phase is performed in nearly linear time and the query phase requires only linear time for single-pair and single-source problems; furthermore, the space complexity is linear for both preprocessing and query phase.

We conducted experiments to evaluate our algorithms. For small networks (n ≤ 1,000,000), our algorithm required only a few minutes for preprocessing, and then answered single-pair and single-source queries in 100 and 300 milliseconds, respectively. All-pairs computation was performed in a few days. For large networks (n ≥ 40,000,000), our algorithm required a few hours for preprocessing, and then answered single-pair and single-source queries approximately in 10 seconds and in a half minutes, respectively.

In comparison to previous studies, for the all-pairs problem, our algorithm uses significantly less memory than any existing algorithm; thus it scales for much larger networks. For the single-pair and the single-source problems, our algorithm requires much fewer random samples than any existing Monte Carlo based algorithm for the same accuracy solution.