Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

SimRank: Similarity Based on Random Walk and Structural Context

  • SimRank: structural-context similarity, i.e., based on the similarity of its neighbors
  • In a directed graph G = (V,E),
    • individual in-neighborhood of v: I(v) = {u | (u, v) ∈ E}
    • individual out-neighborhood of v: O(v) = {w | (v, w) ∈ E}
  • Similarity in SimRank: 

\[s(u,v)=\frac{C}{|I(u)||I(v)|}\sum_{x\epsilon I(u)}\sum_{y\epsilon I(v) }s(x,y) \]

    • Initialization:

\[ s_{0}(u,v)=\left\{\begin{matrix}0, if u\neq v \\ 1,if u=v \end{matrix}\right. \]

    • Then we can compute si+1 from si based on the definition
  • Similarity based on random walk: in a strongly connected component
    • Expected distance:

\[d(u,v)=\sum_{t:(u\rightarrow v)}P[t]l(t)\]

Speaker notes:

Content Tools


There are currently no sources for this slide.