@TOC[目录]
PageRank 是 由佩奇(Larry Page)等人提出 的 Google 最为有名的技术之一
PageRank 是一种基于随机游走 的 评价网站权值的算法
总之， PageRank 是一种十分重要的算法 不管在学术界 还是在产业界
Node Similarity(节点相似度)
假设在一个图G(V,E)中研究两个节点u，v之间的相关性
直观上，u，v之间的相似度高于u，w之间的相似度
可以按计算时用到部分点还是全部点来进行分类
local
Common Neighbors(CN), Jaccard, Adamic-Adar Index
grobal
Personalized PageRank(PPR), SimRank, Katz
事实上 节点相似度在生产过程中有极强的落地场景,尤其是和社交网络分析相关的好友推荐
,另外 还可以运用在 Top-k 的关系发现当中。
local
CN 算法(common neighbor)
一个节点的邻居集合可以表征这个节点的周围结构
规定：
Jaccard
单一的数值对于衡量一个节点的相似度， 可能存在尺度标准不统一的情况
故 jaccard 在 CN 的基础上进行了一个归一化的处理
得到
Adamic-Adar Index
是一种基于节点之间共同邻居的亲密度测算方法。2003年由 Lada Adamic 和 Eytan Adart在 predict links in a social network中提出的，计算亲密度的公式如下：
global
Naive PageRank
PageRank 的核心思想
- 如果一个网页被很多其他网页链接到的话，说明这个网页比较重要，也就是 PageRank 值会相对较高。(很多人推荐你)
- 如果一个 PageRank 值很高的网页链接到一个其他的网页，那么链接到的网页的 PageRank 值也会相应地提高。(大佬推荐你的作用更大)
对应PageRank 背后的两个基本假设：
数量假设：更重要的网页可能被更多的网页链接到。
质量假设：有更高的 PageRank 的网页将会传递更高的权重。
PageRank 算法计算每一个网页的 PageRank 值，然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank 就是估计这个悠闲的上网者分布在各个网页上的概率。
PageRank 模型
将整个 Web 被抽象为一张有向图
转移矩阵
用**转移矩阵（Transition Matrix）**来表示页面以及页面间的连接关系：
性质：
- 矩阵的每一列代表一个具体网页的出链，简单地说就是当前网页向其他网页的链接；
- 矩阵的每一行代表一个具体网页的入链，简单地说就是其他网页向当前网页的链接。
Naive PageRank 计算
陷阱问题
上图中 5、6、7 三个页面构成一个闭环，它们紧密链接成环而没有外出的链接，最终也会导致上网者“深陷于此”。同样的，经过多次跳转，陷阱网页的概率值之和为 1，而其他正常网页的概率值为 0。
随机浏览模型
假定一个上网者从一个随机的网页开始浏览，此时有两种选择：
通过点击当前页面的其他链接开始下一次浏览；
通过在浏览器的地址栏输入新的地址以开启一个新的网页。
其中，上网者通过点击链接开启新页面的概率为 d（d 也称阻尼系数，通常取 0.85）。
此时，PageRank 模型变为：在每一个页面，用户都有 d 的概率通过点击链接进入下一个页面；此外，还有 1 - d 的概率随机跳转，此时跳转到其他页面的概率为 1 / N（当前页面的其他链接数）
参考：
- 如何一口气理解PageRank
- 大图中如何快速计算PPR
- PageRank 笔记
