SimRank

SimRank is a general similarity measure, based on a simple and intuitive graph-theoretic model. SimRank is applicable in any domain with object-to-object relationships, that measures similarity of the structural context in which objects occur, based on their relationships with other objects. Effectively, SimRank is a measure that says that two objects are considered to be similar if they are referenced by similar objects. Although SimRank is widely adopted, it may output unreasonable similarity scores which are influenced by different factors, and can be solved in several ways, such as introducing an evidence weight factor, inserting additional terms that are neglected by SimRank or using PageRank-based alternatives.

SimRank is a general similarity measure, based on a simple and intuitive graph-theoretic model. SimRank is applicable in any domain with object-to-object relationships, that measures similarity of the structural context in which objects occur, based on their relationships with other objects. Effectively, SimRank is a measure that says that two objects are considered to be similar if they are referenced by similar objects. Although SimRank is widely adopted, it may output unreasonable similarity scores which are influenced by different factors, and can be solved in several ways, such as introducing an evidence weight factor, inserting additional terms that are neglected by SimRank or using PageRank-based alternatives. If a = b then s(a, b) is defined to be 1 . Otherwise, s(a, b) = \frac{C}{\left|I(a)\right| \left|I(b)\right|} \sum_{i=1}^{\left|I(a)\right|}\sum_{j=1}^{\left|I(b)\right|} s(I_i(a), I_j(b)) where C is a constant between 0 and 1 . A slight technicality here is that either a or b may not have any in-neighbors. Since there is no way to infer any similarity between a and b in this case, similarity is set to s(a, b) = 0 , so the summation in the above equation is defined to be 0 when I(a) = \emptyset or I(b) = \emptyset . Given an arbitrary constant C between 0 and 1 , let \mathbf{S} be the similarity matrix whose entry [\mathbf{S}]_{a,b} denotes the similarity score s(a,b) , and \mathbf{A} be the column normalized adjacency matrix whose entry [\mathbf{A}]_{a,b}=\tfrac{1} if there is an edge from a to b , and 0 otherwise. Then, in matrix notations, SimRank can be formulated as = \max\{C\cdot (\mathbf{A}^{T} \cdot \cdot ) , \}, where \mathbf{I} is an identity matrix. s_0(a, b) = \begin{cases} 1 \mbox{ } , \mbox{ } \mbox{if } a = b \mbox{ } , \\ 0 \mbox{ } , \mbox{ } \mbox{if } a \neq b \mbox{ } . \end{cases} To compute s_{k+1}(a, b) from s_k(*, *) , we use the basic SimRank equation to get: s_{k + 1}(a, b) = \frac{C}{\left|I(a)\right| \left|I(b)\right|} \sum_{i=1}^{\left|I(a)\right|}\sum_{j=1}^{\left|I(b)\right|} s_k(I_i(a), I_j(b)) for a \ne b , and s_{k+1}(a, b) = 1 for a = b . That is, on each iteration k + 1 , we update the similarity of (a, b) using the similarity scores of the neighbours of (a, b) from the previous iteration k according to the basic SimRank equation. The values s_k(*, *) are nondecreasing as k increases. It was shown in that the values converge to limits satisfying the basic SimRank equation, the SimRank scores s(*, *) , i.e., for all a, b \in V , \lim_{k \to \infty} s_k(a, b) = s(a, b) . The original SimRank proposal suggested choosing the decay factor C = 0.8 and a fixed number K = 5 of iterations to perform. However, the recent research showed that the given values for C and K generally imply relatively low accuracy of iteratively computed SimRank scores. For guaranteeing more accurate computation results, the latter paper suggests either using a smaller decay factor (in particular, C = 0.6 ) or taking more iterations. p^{(k)} = A p^{(k-1)} s(i,j) = \sum_{k=0}^{\infty} C^k \langle p^{(k)}(i), p^{(k)}(j) \rangle Step one can be seen a simplified version of Personalized PageRank. Step two sums up the vector similarity of each iteration. Both, matrix and local representation, compute the same similarity score. CoSimRank can also be used to compute the similarity of sets of nodes, by modifying p^{(0)}(i) . \text{Partial}_{I(a)}^{s_{k}}(j)=\sum_{i \in I(a)}s_{k}(i,j), \qquad (\forall j \in I(b)) and then s_{k+1} (a,b) is iteratively computed from \text{Partial}_{I(a)}^{s_{k}}(j) as s_{k+1}( a,b )=\frac{C} \sum_{j \in I(b) } \text{Partial}_{I(a)}^{s_{k}}(j). Consequently, the results of \text{Partial}_{I(a)}^{s_{k}}(j) , \forall j \in I(b) , can be reused later when we compute the similarities s_{k+1}(a,*) for a given vertex a as the first argument.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1364355320 under CC BY-SA 4.0; modifications have been made.