FANDOM


Symbol opinion vote Comment: CoSimRank may be notable, but we require multiple, reliable, arm's length sources to provide evidence of it as described above. Thanks. j⚛e deckertalk 15:56, 9 August 2014 (UTC)

CoSimRank

CoSimRank is a variant of SimRank with the advantage of also having a local formulation, i.e. CoSimRank can be computed for a single node pair.[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. Then, in matrix notations, CoSimRank can be formulated as:

$ {{\mathbf{S}}}= C\cdot (\mathbf{A}^{T} \cdot {{\mathbf{S}}}\cdot {{\mathbf{A}}} ) + {{\mathbf{I}}}, $

where $ \mathbf{I} $ is an identity matrix. To compute the similarity score of only a single node pair, let $ p^{(0)}(i) = e_i $, with $ e_i $ being a vector of the standard basis, i.e., the $ i $-th entry is 1 and all other entries are 0. Then, CoSimRank can be computed in two steps:

  1. $ p^{(k)} = A p^{(k-1)} $
  2. $ 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) $.

References

  1. S. Rothe and H. Schütze. CoSimRank: A Flexible & Efficient Graph-Theoretic Similarity Measure. In ACL '14: Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1392-1402 . [1]
This article uses material from the Wikipedia article Draft:CoSimRank, that was deleted or is being discussed for deletion, which is released under the Creative Commons Attribution-ShareAlike 3.0 Unported License.
Author(s): Joe Decker Search for "Draft:CoSimRank" on Google
View Wikipedia's deletion log of "Draft:CoSimRank"
Wikipedia-logo-v2