SimRank is an influential link-based similarity measure that
has been used in many fields of Web search and sociometry.
The best-of-breed method by Kusumoto et al. [7], however,
does not always deliver high-quality results, since it fails to
accurately obtain its diagonal correction matrix D. Besides,
SimRank is also limited by an unwanted“connectivity trait”:
increasing the number of paths between nodes a and b often
incurs a decrease in score s(a, b). The best-known solution,
SimRank++ [1], cannot resolve this problem, since a revised
score will be zero if a and b have no common in-neighbors.
In this paper, we consider high-quality similarity search.
Our scheme, SR#, is efficient and semantically meaningful:
(1) We first formulate the exact D, and devise a “varied-D”
method to accurately compute SimRank in linear memory.
Moreover, by grouping computation, we also reduce the time
of [7] from quadratic to linear in the number of iterations.
(2) We design a “kernel-based”model to improve the quality
of SimRank, and circumvent the “connectivity trait” issue.
(3) We give mathematical insights to the semantic difference
between SimRank and its variant, and correct an argument
in [7]: “if D is replaced by a scaled identity matrix (1−γ)I,
top-K rankings will not be affected much”. The experiments
confirm that SR# can accurately extract high-quality scores,
and is much faster than the state-of-the-art competitors.