PageRank算法原理
浏览数：56 /
时间：2015年06月08日
定义问题
某网页 i 的PageRank 定义为上网者某一次点击鼠标到达网页 i 概率，记做
。
比如，某网页的 PageRank 是0.000005 意味着一个人随机点击鼠标到达该网页的概率是 0.000005 。
在网络世界里，对某一次点击来说，所有网页的 PageRank 之和为1 。
建模
网络世界中的各个节点可以表达成一幅巨大的有向图。如果节点 i 能链接到节点 j，则从i到 j有一条有向边。对于某节点 i ，它有一定的出度和入度，出度指的是从该点出发的有向边的数量，入度指的是到达该点的有向边的数量。比如上图，节点 A 的入度是3 ，出度是 2 。定义假设节点 i的出度为 L(i) ，能到达节点 i的所有节点的集合为 IN(i) 。
数学推导
假如上网者是从别的节点j 跳转到某节点 i 的，那么因为节点 j的出度是 L(j) ，在概率平均的情况下，有 PR(j)/L(j) 的概率从j 跳转到 i，所以从别的节点链接到节点 i 的概率就是：
这里的 j 属于能到达节点 i的所有节点的集合。
那么扩展到更一般的情况：假设
指第t 次鼠标点击后，网页 i 出现的概率；那么在完成第 t 次点击后，用户有可能继续点击链接，也有可能在浏览器里新打开了一个标签输入 URL ，或者直接关掉电脑去找女朋友了（两天后他又上了网，开始了 t+1 次点击）。 反正无论怎样，用户在 t+1 次点击时得到的网页，有一定概率 d 是从第t 次点击得到的网页中链接过去的，也有可能是输入一个网址得到的，易得这个概率是 1-d 。
假设互联网中所有网页数量是 N ，那么随机进入网页 i的概率就是 1/N ，所以：
当 t很大时， t+1 时的PR(i) 和 t时的 PR(i) 可以认为相同，也就得到了下面的公式：
用这个公式直接计算 PageRank 是复杂度极大的，但我们可以把它转化成矩阵的计算。
假设 
，那么
这里 1 是一个N 行的全 1矩阵 
现在的关键是求 M ，根据上面的推导可知：
所以，假设图得邻接矩阵为 A ，所有节点的出度矩阵为 K ，那么
，所以代入 M 进
可得所有节点的 PageRank。
定义问题
某网页 i 的PageRank 定义为上网者某一次点击鼠标到达网页 i 概率，记做 。
。比如，某网页的 PageRank 是0.000005 意味着一个人随机点击鼠标到达该网页的概率是 0.000005 。
在网络世界里，对某一次点击来说，所有网页的 PageRank 之和为1 。
建模
网络世界中的各个节点可以表达成一幅巨大的有向图。如果节点 i 能链接到节点 j，则从i到 j有一条有向边。对于某节点 i ，它有一定的出度和入度，出度指的是从该点出发的有向边的数量，入度指的是到达该点的有向边的数量。比如上图，节点 A 的入度是3 ，出度是 2 。定义假设节点 i的出度为 L(i) ，能到达节点 i的所有节点的集合为 IN(i) 。
数学推导
假如上网者是从别的节点j 跳转到某节点 i 的，那么因为节点 j的出度是 L(j) ，在概率平均的情况下，有 PR(j)/L(j) 的概率从j 跳转到 i，所以从别的节点链接到节点 i 的概率就是：
这里的 j 属于能到达节点 i的所有节点的集合。
那么扩展到更一般的情况：假设 指第t 次鼠标点击后，网页 i 出现的概率；那么在完成第 t 次点击后，用户有可能继续点击链接，也有可能在浏览器里新打开了一个标签输入 URL ，或者直接关掉电脑去找女朋友了（两天后他又上了网，开始了 t+1 次点击）。 反正无论怎样，用户在 t+1 次点击时得到的网页，有一定概率 d 是从第t 次点击得到的网页中链接过去的，也有可能是输入一个网址得到的，易得这个概率是 1-d 。
指第t 次鼠标点击后，网页 i 出现的概率；那么在完成第 t 次点击后，用户有可能继续点击链接，也有可能在浏览器里新打开了一个标签输入 URL ，或者直接关掉电脑去找女朋友了（两天后他又上了网，开始了 t+1 次点击）。 反正无论怎样，用户在 t+1 次点击时得到的网页，有一定概率 d 是从第t 次点击得到的网页中链接过去的，也有可能是输入一个网址得到的，易得这个概率是 1-d 。假设互联网中所有网页数量是 N ，那么随机进入网页 i的概率就是 1/N ，所以：
当 t很大时， t+1 时的PR(i) 和 t时的 PR(i) 可以认为相同，也就得到了下面的公式：
用这个公式直接计算 PageRank 是复杂度极大的，但我们可以把它转化成矩阵的计算。
假设 ，那么
，那么这里 1 是一个N 行的全 1矩阵
现在的关键是求 M ，根据上面的推导可知：
所以，假设图得邻接矩阵为 A ，所有节点的出度矩阵为 K ，那么
，所以代入 M 进 可得所有节点的 PageRank。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
