CS224W--Graph as matrix - PageRank

Content

1. PageRank (lecture 4.1 & 4.2)
2. Random walk and restarts (lecture 4.3)
3. Matrix factorization and node embeddings (lecture 4.4)

1. PageRank

web page contains in-links and out-links

The importance of page can be defined as the number of in-links, AKA links as votes

The flow model

Link as vote

Definitions:

• Rank $r_j=\sum _{i\to j}\frac{r_i}{d_i}$, where $d_i$ is out-defree of node i.
• Stochastic adjacency matrix $M_{ij}=\frac{1}{d_j}$, is a column stochastic matrix (columns sum to 1).
• Rank vector $r$, where $\sum _i{r}_i=1$.
• $r=Mr$.

Connect to random walk

Definitions:

• $p(t)$ probability distribution over pages
• $p(t+1)=M\dot{p}(t)$, $p(t)$ is a stationary distribution of a random walk.

solving eigenvector equation $\lambda x=Ax$

Similarly, the rank vector $r$ can be seen as the eigenvector of $M$ with an eigenvalue of 1.