PageRank算法

1. 关于PageRank

• PageRank算法是图的链接分析（link-analysis）的代表性算法，属于图数据上的无监督学习
• 最初为互联网网页重要度的计算方法
• 基本思路：在一个有向图上定义一个随机游走模型。在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这个时候各个节点的平稳概率值就是其PageRank值，表示节点的重要度。
• 随机游走的过程形成了一个一阶马尔科夫链，是一个迭代的过程，不断计算各个网络节点的PageRank值，直到收敛为止。
• 直观的，指向某节点的路径越多，该节点就越重要，PageRank值越高，游走到该节点的概率越大。
• PageRank值依赖于网络的拓扑结构，一旦网络的拓扑确定，PageRank值就确定

2. 有向图

• 记为$G=（V，E）$，$V$和$E $分别表示节点和有向边的集合
• 互联网可以近似看作一个有向图，网页是节点，超链接是边
• 强连通图：从有向图任意一点出发可以到达其他任何一个节点
• 周期性节点：从有向图的某个节点出发返回到这个节点路径的长度都是某个自然数k的倍数