Current Slide

• 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)\]