PageRank 计算过程
4.修改概率转移矩阵； 5.迭代求解PageRank 值。
10
54 计算方法
左图中,链接关系分别为 ：12, 13 , 14, 21, 24, 42, 43
左图为该有向图的邻接矩阵，其中，邻 接矩阵M的每一行代表的是每个节点的 出链
11
54 计算方法
对上述的邻接矩阵M，计算其链接概率矩阵，即 对出链进行归一化，得到链接概率矩阵M’，这 样，即表示有多少概率链接到其他的点。
PageRank
小组成员： 课程：数据挖掘
1 概况介绍
2 PageRank算法主要思想
my contents here
目录
3 PageRank 的两个假设
4 PageRank 的计算方法
ቤተ መጻሕፍቲ ባይዱ
5 PageRank的Python表示
6 总结
1
01
概况介绍
PageRank，网页排名，又称网页级别、Google左侧排名或佩奇排名
2
1 概况介绍
简介
PageRank算法是一种由根据网页之间相互的超链接 计算的技术，由Google的创始人拉里·佩奇和谢尔 盖·布林于1998年在斯坦福大学发明出来。PageRank算 法作为网页排名的要素之一，以Google公司创办人拉 里·佩奇（Larry Page）之姓来命名。Google用它来体 现网页的相关性和重要性，在搜索引擎优化操作中是 经常被用来评估网页优化的成效因素之一。PageRank通
。
如果排名高A的网页指向某个网页B，则网 页B的排名也较高，即网页B的排名受指向 其的网页的排名的影响。简单的说，一个高 等级的页面可以使其他低等级页面的等级提
升。
5
25 PageRank算法的主要思想 概括：投票和关联性就是 PageRank 的概念。 给CNN 投票增加了 CNN Pagerank， 的 PageRank级别同时也影响着它为 CNN 投票多大程度影响了CNN 的 PageRank。
的是网页的总数，int(i)表示的是指向网页i的网页集合，out(j)表示的是网页j 指向的网页集合
14
05
PageRank的Python表示
Using python to represent PageRank
15
5 用python表示PageRank
16
45 用python表示PageRank
6
03
PageRank 的两个假设
Two hypotheses of PageRank
7
3 两个假设
数量假设 在web图模中，如果越多的网页指向A，即A的入链数量越多，
Quantity hypothesis
则该网页越重要；
如果指向A的网页质量越高，则A越重要，即权重因素不同。
质量假设
Math hypothesis
3 过网络浩瀚的超链接关系来确定一个页面的等级。
02
PageRank算法主要思想
Two main ideas of PageRank algorithm
4
2 PageRank算法的主要思想
A
B
PageRank通过网络浩瀚的超链接关系来确定一 个页面的等级。Google把从A页面到B页面的链 接解释为A页面给B页面投票，Google根据投票 来源（甚至来源的来源，即链接到A页面的页 面）和投票目标的等级来决定新的等级。如果 多个网页指向某个网页A，则网页A的排名较高
Google将糅合入Title标识、Keywords关键字标识等因素 的PageRank结果来调整搜索结果，使得“更加重要/等级更 高”的网站呈现在检索结果中，从而提高搜索结果的相关 度、质量。PageRank的结果从0到10，10级为满分。PR值 越高说明网页越重要/受欢迎。Google将自身PR值定为10。
对上述的网页链接概率矩阵M’求转置，即可 得到概率转移矩阵P。
概率转移矩阵P可以描述一个用户在网上的下
一步的访问行为。若此时初始化用户对每一个
网页节点的访问概率相等，即都为1/4，则当该
12
用户下一次访问各节点的概率为 : V’=P*v
34 计算方法
但是，此时存在这样的一个问题，一个用户不可能一直按照链接进行 操作，有时会重新进入新的页面，即以一定的概率按照转移概率浏览网 页节点。在上述转移矩阵中加入跳出当前链接的概率α，此时转移矩阵 变为：
链接概率通常取值为常数0.85。最终通过迭代公式：v’ = Av 求解 PageRank值，当v’和v的误差在一定的范围内，即为最终的PageRank值。
13
54 计算方法
最终 PageRank 值为：
对于上述的PageRank算法，其计算公式可以表示为：
公式
其中，PR(i)表示的是图中i节点的PageRank 值，α表示转移概率，N表示
17
45 用python表示PageRank
18
06
总结
summary
19
6 总结
总结
网页排序中，因为来自排序靠前网页的链接更有分量，但该网页本身对其它 网页的排序也是有贡献的。用户又会存在自己的偏好，不可能以相同几率访 问一个网页所有链接。所以佩奇和布林做了这样的假定：在该虚拟用户访问 了一个网页后，下一步将有相同的几率访问被该网页链接的任何一个其他网 页。考虑到我们这一虚拟用户实际上是对所有互联网漫游者所做的平均意义 上的代表，而最终的网页排序，则是由用户在网络上漫游了很长时间--理论 上是无限时间后--访问各网页的几率分布来决定，访问几率越大的网页排序 则越靠前。也就是说一个页面的PageRank值是由其他页面的PR值计算得到的。 Google通过重复计算每个页面的PR值，给每个页面一个初始的非零随机PR值，
现实中一个具体的假设案例是：一篇论文被诺贝尔奖得主所引用， 显 然要比被普通研究者所引用更说明其价值；一篇论文被100位学者引用， 显然要比只有一位普通学者引用之更有价值。
8
04
PageRank 的计算方法
method of PageRank
9
4 计算方法
1.将有向图转换成图的邻接矩 阵M； 2.计算出链接概率矩阵； 3.计算概率转移矩阵；
20 那么经过不断地迭代计算，最终每个页面的PR值将趋于稳定，得到最优
解。这就是PageRank的奇妙所在，以及为何搜索引擎使用它的原因。
谢谢观看
THANKS