[学习笔记]PageRank算法

参考资料：改变世界的谷歌PageRank算法

pagerank算法用于计算节点重要度

思想

如果网页被更多的入度(被引用)，则网页更重要。
被重要网站引用比被普通网站引用更加凸显重要性。
所以考虑一个网站是否重要，需要看引用它的网站是否重要，这就成了一个递归的问题。

理解pagerank的五个角度

迭代求解线性方程组

例子

这里看上去有三个方程，三个未知数，其实只有2个方程。
虽然高斯消元可以求解，但是可扩展性较差。
节点j的rank值$r_j$是考虑所有到$j$的节点的rank值，各自除以它的出度，再求和。

迭代求解

迭代左乘M矩阵

迭代的过程用矩阵表示：(左边的矩阵的i行j列$A_{ij}有非零值$表示存在第j个节点到第i个节点的有向边)

左边的矩阵称为列概率矩阵(列转移矩阵/列替代矩阵，column stochastic matrix)
右边的向量叫pagerank向量

矩阵的特征向量

迭代公式：
$$r=M\cdot r$$其实可以看作是
$$1\cdot r=M\cdot r$$
从这个角度看，pagerank向量就是M矩阵的特征值为1的特征向量。

对于Column Stochastic矩阵，由Perreon-Frobenius定理，最大的特征值就是1，且存在唯一的主特征向量(特征值1对应的特征向量)，向量所有元素求和为1。
通过幂迭代的方式，可以快速求解pagerank向量。

随机游走

随机游走->计数求和->归一化为概率，得到的就是pagerank向量。

马尔科夫链

求解pagerank

收敛性分析

1. 是否收敛-收敛，收敛到同一个结果

Ergodic Theorem

根据Ergodic Theorem，对于不可约(irreducible)和非周期(aperiodic)的马尔可夫链：
1.存在一个唯一的稳定的马尔科夫分布
2.并且所有初始分布收敛到同一个分布

可约(reducible)马尔可夫链和不可约马尔可夫链

可约是存在孤立的状态
不可约是所有状态都可达

周期马尔可夫链和非周期马尔可夫链

2.结果是不是代表重要度-两类问题

Spider trap问题

所有的出度边都在group里面，导致这个group吸收了所有的重要度

dead end问题

没有出度，重要度最终为0

对于这两种情况，即使收敛了，也不是合理的网络重要度。

例子

解决办法

spider trap问题的解决办法

dead end的解决办法

最终解决办法

pagerank的升级-mapreduce的工作

pagerank算法用于计算节点相似度-用于推荐系统

给定：一个bipartite graph用于表示用户和商品的交互
目标：寻找与指定节点最相似的节点
假设：被同一个用户访问过的节点，更可能是相似的

pagerank，随机游走视角的启发

pagerank的一种解释是：随机游走，并有概率随机传送到网络中的任意一个节点，继续游走
Topic-Specific PageRank(也称为personalized pagerank)：随机游走，并有传送到指定的一些节点，继续游走
random walks with restarts：随机游走，并有传送到指定的一个节点，继续游走

随机游走访问次数-相似性的度量

给定一个节点集query_nodes，模拟一个随机游走：

• 记录访问次数
• 在概率$\alpha$下，在query_nodes中重启walk
• 有高访问次数的节点则和query_nodes中的点有更高的相似性

伪代码

优点

代码实战

参考资料：https://www.bilibili.com/video/BV1Wg411H7Ep/?p=16&spm_id_from=pageDriver