Page Rank: Graph as Matrix
在google中，会对页面的重要性进行排序，这节课就是讲的page rank及相关引申。
前置知识--马尔可夫矩阵
马尔科夫矩阵（Markov Matrices）的定义：
- 矩阵中的所有元素大于 0 且 小于等于 1
- 各列的元素相加之和为 1 （也有一些教材用行之和为 1 ）
有个显著的特点是，矩阵一定存在一个值为1的特征值。
Page rank
各种静态图的中的超链接会构成一个有向图。在page-rank中的一个重要思想是，当浏览者在某个页面中是，会随机点击指向其他的超链接，于是有了一种流模型。
同时我们定义一个页面的重要性和其他页面的重要性有关，重要性在页面之间流动。一个被更多页面指向的页面有更高的排名，从而产生一个迭代重要性。
The flow model
我们定义每个节点j的rank
\[r_j = \sum_{i\rightarrow j} \frac{r_i}{d_i} \]其中，\(d_i\)是节点i的出度，\(r_i\)是节点i的rank
一个栗子
我们可以看到，这样的一个\(M\)的就是最开始的马尔可夫矩阵。并且r则为特征值为1的特征向量。
connection to Random Walk
原文介绍了从随机游走的过程理解流过程，得出的结论和上述类似。
假设最后会得到一个静态概率分别
\[p(t+1) = M \cdot p(t) = p(t) \]Tow problems of Page Rank
- dead ends：最后一个节点没有出度，则重要性会流失不见
- Spider traps：最后一个节点只有自我循环，则重要性会聚集到那个节点上。
solution--teleport
假设浏览者会有一定的概率\(\beta（0.8、0.9）\)浏览节点的出节点，否则会随机跳到任意一个节点上。
利用数学表达就是：
\[r_j = \sum_{i \rightarrow j} \beta \frac{r_i}{d_i} + (1- \beta)\frac{1}{N} \]
最后的G也是一个马尔可夫矩阵。
当然上述的rank计算，可以是迭代计算，最后r得到收敛。
Random Walk with Restarts and Personalized PageRank
计算中，和Page Rank最大不同的就是\(\beta\)后的N*N矩阵的设置。
- Random Walk with Restarts：在浏览的点设为1，其他全为0
- Personalized PageRank：依靠一定的策略定制矩阵，比如推荐系统中的点击量（记得归一化）或为下次游走的权重，
some limitations of node embeddings and random walks
- Cannot obtain embeddings for nodes not in the training set
- Cannot capture structural similarity
- Cannot utilize node, edge and graph features
Summary
