• 欢迎光临~

Page Rank: Graph as Matrix

开发技术 开发技术 2022-10-06 次浏览

Page Rank: Graph as Matrix

在google中,会对页面的重要性进行排序,这节课就是讲的page rank及相关引申。

前置知识--马尔可夫矩阵

马尔科夫矩阵(Markov Matrices)的定义:

  • 矩阵中的所有元素大于 0 且 小于等于 1
  • 各列的元素相加之和为 1 (也有一些教材用行之和为 1 )

有个显著的特点是,矩阵一定存在一个值为1的特征值。

Page rank

各种静态图的中的超链接会构成一个有向图。在page-rank中的一个重要思想是,当浏览者在某个页面中是,会随机点击指向其他的超链接,于是有了一种模型。

同时我们定义一个页面的重要性和其他页面的重要性有关,重要性在页面之间流动。一个被更多页面指向的页面有更高的排名,从而产生一个迭代重要性。Page Rank: Graph as Matrix

The flow model

我们定义每个节点j的rank

[r_j = sum_{irightarrow j} frac{r_i}{d_i} ]

其中,(d_i)是节点i的出度,(r_i)是节点i的rank

一个栗子

Page Rank: Graph as Matrix

我们可以看到,这样的一个(M)的就是最开始的马尔可夫矩阵。并且r则为特征值为1的特征向量。

connection to Random Walk

原文介绍了从随机游走的过程理解流过程,得出的结论和上述类似。
Page Rank: Graph as Matrix

[p(t+1) = M cdot p(t) ]

假设最后会得到一个静态概率分别

[p(t+1) = M cdot p(t) = p(t) ]

Tow problems of Page Rank

  • dead ends:最后一个节点没有出度,则重要性会流失不见
  • Spider traps:最后一个节点只有自我循环,则重要性会聚集到那个节点上。
    Page Rank: Graph as Matrix

Page Rank: Graph as Matrix

solution--teleport

假设浏览者会有一定的概率(beta(0.8、0.9))浏览节点的出节点,否则会随机跳到任意一个节点上。

利用数学表达就是:

[r_j = sum_{i rightarrow j} beta frac{r_i}{d_i} + (1- beta)frac{1}{N} ]

Page Rank: Graph as Matrix

最后的G也是一个马尔可夫矩阵。

当然上述的rank计算,可以是迭代计算,最后r得到收敛。

Random Walk with Restarts and Personalized PageRank

计算中,和Page Rank最大不同的就是(beta)后的N*N矩阵的设置。

  • Random Walk with Restarts:在浏览的点设为1,其他全为0
  • Personalized PageRank:依靠一定的策略定制矩阵,比如推荐系统中的点击量(记得归一化)或为下次游走的权重,
    Page Rank: Graph as Matrix

some limitations of node embeddings and random walks

  • Cannot obtain embeddings for nodes not in the training set
  • Cannot capture structural similarity
    Page Rank: Graph as Matrix
  • Cannot utilize node, edge and graph features

Summary

Page Rank: Graph as Matrix

程序员灯塔
转载请注明原文链接:Page Rank: Graph as Matrix
喜欢 (0)