Vertex set: metrics, norms

Similarity measures between u and v are inverses of distance metrics.

Based on paths and random walks

• (shortest path).

Katz measure

$sim(u,v)=\sum _{l=1}^{\mathrm{\infty }}{\beta }^l|path{s}_{u,v}(l)|$. Matrix of scores, $K=\sum _{i=1}^{\mathrm{\infty }}{\beta }^i{A}^i$.

The damping parameter

$K=(I-\beta A{)}^{-1}-I$ if the sum converges. Use \(A = U\EW U^{}\): EW decomposition, with ${\lambda }_i$ ordered in descending order. \(\sum_{i=1}^{\infty} \gb^{i}A^{i} = U(\sum_{i=1}^{\infty} \gb^{i}\EW^{i})U^{}\) does not converge $\mathrm{\forall }\beta \ge 0$ and multiplication by $\mathrm{\infty }$ is not well defined. Condition for convergence: $\beta {\lambda }_1<1$.

But, for $\beta >1$ the intuition of weighting longer paths less does not hold.

Variants of Katz

Similarly can use $e^{-\beta A}$.

Truncated Katz usually used: $\sum _{l=1}^k{\beta }^l{A}^l$: $O(l{n}^{2}nz(A))$ op instead of $O(n^3)$ inverse finding.

Hitting time

$-h_{u,v}$; normed by stationary distribution: $-h_{u,v}{\pi }_v$: to take care of skewing of hitting time due to large ${\pi }_v$. - Commute time: $-h_{u,v}-h_{v,u}$; stationary distr normed: $-h_{u,v}{\pi }_v-h_{v,u}{\pi }_u$.

Rooted PageRank

Random walk can get lost in parts of graph away from u and v; so do random resets and return to u with probability a at each step.

SimRank

A recursive definition: 2 nodes are similar to the extant that they are joined to similar nodes. $sim(x,x)=1;sim(x,y)=\frac{\sum _{a\in \mathrm{\Gamma }(x)}\sum _{b\in \mathrm{\Gamma }(y)}sim(a,b)}{|\mathrm{\Gamma }(x)||\mathrm{\Gamma }(y)|}$.

Common neighbor based

Common neighbors: $|\mathrm{\Gamma }(u)\cap \mathrm{\Gamma }(v)|$: same as taking inner product of rows in adj matrix M corresponding to u and v. (Jaccard): $\frac{\mathrm{\Gamma }(u)\cap \mathrm{\Gamma }(v)}{\mathrm{\Gamma }(u)\cup \mathrm{\Gamma }(v)}$: pick a feature at random, see probability that it is a feature of both u and v. (Adamic/ Adar): $\sum _{z\in \mathrm{\Gamma }(u)\cap \mathrm{\Gamma }(v)}\frac{1}{\log |\mathrm{\Gamma }(z)|}$: greater wt to rare features present in both.