PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs

Zhewei Wei, Xiaodong He, Xiaokui Xiao +4

{\it SimRank} is a classic measure of the similarities of nodes in a graph. Given a node $u$ in graph $G=(V,E)$, a {\em single-source SimRank query} returns the SimRank similarit…