Efficient SimRank computation via linearization

Abstract

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 new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem.By using this technique, we can solve many SimRank problems, such as single-pair compuation, single-source computation, all-pairs computation, top k searching, and similarity join problems, efficiently.