In the paper "Accelerating pairwise SimRank estimation over static and dynamic graphs", Wang et al. motivate that sometimes people may issue a set of similarity queries, which may not be restricted to a particular source. For example, people may want to know "Which two scientists in the DB area, who have not collaborated with each other before, would likely collaborate in the future?", or "Which scientists in DB, who have collaborated with AI researchers before, would keep on collaborating with other AI scientists?"
Wang et al. note that iterative deterministic methods have two drwabacks. One is its BFS fixed-order expansion, which is not optimized for the local structure of query nodes. It may also contain unnecessary computation, which contributes little to the final SimRank score. Second, as k increases, the number of k-hop neighbors grows exponentially.
Most recent solutions for dynamic SimRank query are based on its probabilistic interpretation: s(a,b) is the expected f-meeting time of two revers