《PageRank算法.pdf》由会员分享，可在线阅读，更多相关《PageRank算法.pdf（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。
1、PageRankPageRank算法算法 线性代数理论的经济学应用系列专题 一一. . 背景介绍背景介绍 Google的创始人拉里的创始人拉里佩奇和谢尔盖佩奇和谢尔盖布林于布林于19981998年在年在 斯坦福大学提出了斯坦福大学提出了PageRank算法算法。 该算法以拉里该算法以拉里佩奇（佩奇（Larry Page）之姓来命名。）之姓来命名。 是是Google专有的算法，用于衡量特定网页相对于搜索引专有的算法，用于衡量特定网页相对于搜索引 擎索引中的其他网页而言擎索引中的其他网页而言的的重要程度。重要程度。 PageRankPageRank让链接来“投票”，指向某个页面的超链接相让链接来“
2、投票”，指向某个页面的超链接相 当于对该页投一票。当于对该页投一票。 结合所有结合所有网页重要性网页重要性和和相关性相关性指标，指标，Google将最相关和将最相关和 最可靠的结果放在搜索结果的顶端。最可靠的结果放在搜索结果的顶端。 问题：如何问题：如何度量网页本身的度量网页本身的重要性？重要性？ （1 1）如果）如果一个网页被很多其他网页一个网页被很多其他网页链接，说明链接，说明这个这个网页网页 比较比较重要，也就是重要，也就是PageRankPageRank值会相对值会相对较高。较高。 （2 2）如果一个）如果一个PageRankPageRank值很高的网页链接到一个其他值很高的网页链接到
3、一个其他 的网页，那么被链接到的网页的的网页，那么被链接到的网页的PageRankPageRank值也会相应地提高。值也会相应地提高。 二二. PageRank. PageRank算法算法 1. 算法思想：算法思想： AB CD ( )( )() ( ) 213 PR BPR CPR D PR A 假设一个由只有假设一个由只有4 4个页面组成的集合：个页面组成的集合：A A，B B，C C和和D D。 如果所有页面都链向如果所有页面都链向A A，那么，那么A A的的PRPR（PageRankPageRank）值）值 将是将是B B，C C及及D D的和的和。 若此刻在若此刻在浏览浏览B B网页
4、，那么下一步他打开网页，那么下一步他打开A A网页网页还还 是是C C网页网页在统计上应该是相同概率在统计上应该是相同概率的的。 二二. PageRank. PageRank算法算法 1. 算法思想：算法思想： 因此因此A A网页的网页的PageRankPageRank值定义值定义为：为： 二二. PageRank. PageRank算法算法 A AB B C CD D 0111 0001 0101 0000 G 记矩阵记矩阵G G的列和、行和分别是的列和、行和分别是 , jij i cg j iji gr 它们分别给出了页面它们分别给出了页面j j的链出链接数目和链入链接数目的链出链接数目和
5、链入链接数目 2 2. . 用用邻接矩阵邻接矩阵表示互联网表示互联网 显然，如果网页有显然，如果网页有N N 个，则矩阵为个，则矩阵为N NN N 的的0 0- -1 1方阵。方阵。 将互联网定义成有向图，用将互联网定义成有向图，用邻接矩阵邻接矩阵来表示图，即：来表示图，即： 定义邻接矩阵为定义邻接矩阵为G G，若网页，若网页j j有指向网页有指向网页i i的超链接，的超链接， 则则反之反之。 = , ,=0 0 假设在假设在上网的时侯浏览页面并选择下一个页面，这个上网的时侯浏览页面并选择下一个页面，这个 过程与过去浏览过哪些页面无关，而仅依赖于当前所在过程与过去浏览过哪些页面无关，而仅依赖于
6、当前所在 的页面，那么这的页面，那么这一过程一过程可以认为是一个有限状态、离散可以认为是一个有限状态、离散 时间的时间的随机过程。随机过程。 (), ij Aa , ij ij j g a c 定义状态转移概率矩阵为：定义状态转移概率矩阵为：其中其中 A AB B C CD D 01/ 211/3 0001/3 01/ 201/3 0000 A 0111 0001 0101 0000 G ， 二二. PageRank. PageRank算法算法 3. 3. 用用状态转移矩阵状态转移矩阵表示页面浏览随机过程表示页面浏览随机过程 根据这个矩阵，我们能够计算出根据这个矩阵，我们能够计算出经过经过 一
7、一次网页跳转之后，用户访问到次网页跳转之后，用户访问到每个每个 网页网页的的概率分布。概率分布。 则经过一次状态转移后，四个网站的访问概率更新为：则经过一次状态转移后，四个网站的访问概率更新为： 假设初始四个网站的访问概率为假设初始四个网站的访问概率为0 1 1 1 1 , 4 4 4 4 T 10 01/ 211/31/ 4 0001/31/ 4 , 01/ 201/31/ 4 00001/ 4 A 二二. PageRank. PageRank算法算法 3. 3. 用用状态转移矩阵状态转移矩阵表示页面浏览随机过程表示页面浏览随机过程 01/ 211/3 0001/3 01/ 201/3 00
8、00 A 类似可得类似可得 2 120 n nnn AAA 2 210 1/ 4 0 , 1/ 24 0 AA 3 320 1/24 0 , 0 0 AA 4 4056 00 00 ,. 00 00 n A A AB B C CD D 终止点问题：终止点问题：A A网站不指向任何链接，导致网站不指向任何链接，导致 最终各网站访问概率为最终各网站访问概率为0 0。 二二. PageRank. PageRank算法算法 4.4. 特殊情况：终止点问题和陷阱问题特殊情况：终止点问题和陷阱问题 01/211/3 0001/3 01/201/3 0000 A ， 陷阱问题：陷阱问题：A A网站只指向它自
9、己：最终其他各网站网站只指向它自己：最终其他各网站 访问概率为访问概率为0 0，概率分布概率分布值全部值全部转移转移到到A A上来。上来。 A AB B C CD D 11/ 211/3 0001/3 01/ 201/3 0000 A 10234 17/ 2423/ 241 1/1200 , 5/ 241/ 240 000 A 二二. PageRank. PageRank算法算法 4.4. 特殊情况：终止点问题和陷阱问题特殊情况：终止点问题和陷阱问题 5. 5. 解决解决终止点问题和陷阱终止点问题和陷阱问题的办法问题的办法 在走到一个终结网页或者一个陷阱在走到一个终结网页或者一个陷阱网页，用户
10、会在网页，用户会在浏览器浏览器 的地址随机输入一个地址的地址随机输入一个地址，而，而在地址栏输入而跳转到各个在地址栏输入而跳转到各个 网页的概率是网页的概率是1/n1/n。 假设假设上网者每一步查看当前网页的概率上网者每一步查看当前网页的概率为为d d，d d为为阻尼系数阻尼系数 （damping factordamping factor）。那么）。那么他从浏览器地址栏跳转的概率他从浏览器地址栏跳转的概率 为为( (1 1- -d)d)，于是原来的迭代公式转化为：，于是原来的迭代公式转化为： 10 (1) nn dAd 二二. PageRank. PageRank算法算法 佩奇和布林证明了上述
11、迭代公式的解佩奇和布林证明了上述迭代公式的解的存在性的存在性，唯一性，唯一性， 收敛性。经过大量实验，建议收敛性。经过大量实验，建议d=0.85.d=0.85. 含陷阱点的计算过程收敛于：含陷阱点的计算过程收敛于： 0.250.640.85 0.250.110.09 0.250.210.07 0.250.040.04 含含终止点的计算过程收敛于：终止点的计算过程收敛于： 0.250.430.13 0.250.110.05 0.250.210.07 0.250.040.04 二二. PageRank. PageRank算法算法 AB CD A AB B C CD D 根据根据MarkovMark
12、ov链的基本性质，对于链的基本性质，对于正则正则MarkovMarkov链（即不存链（即不存 在陷阱和终止情况）在陷阱和终止情况）， 存在存在平稳分布平稳分布， 满足满足 T N xxx),( 21 ,A 1. i i x 表示表示在极限状态（转移次数趋于无限）下各网页被访在极限状态（转移次数趋于无限）下各网页被访 问的概率分布。问的概率分布。 i x 定义为网页的定义为网页的PageRankPageRank向量，向量， 表示表示第第i i个网页的个网页的PageRankPageRank值。值。 二二. PageRank. PageRank算法算法 6 6. . 从特征值和特征向量的角度理解从
13、特征值和特征向量的角度理解 求矩阵求矩阵A A的特征值的特征值1 1 对应的对应的特征向量特征向量 三三. . 计算实例计算实例 下图某7个网页之间的链接关系图，试计算它们的PageRank值。 第一步：得到网页链接图的邻接矩阵 0110110 1011000 1001100 1000100 1001011 0000100 1000000 G 第二步：得到状态转移概率矩阵A 011/ 201/ 41/ 20 1/501/ 21/3000 1/5001/3 1/ 400 1/50001/ 400 1/5001/301/ 21 00001/ 400 1/5000000 A 三三. . 计算实例计算
14、实例 下图某7个网页之间的链接关系图，试计算它们的PageRank值。 第三步：若不考虑随机跳转时，求出状态转移第三步：若不考虑随机跳转时，求出状态转移 概率矩阵概率矩阵A A的特征值的特征值1 1对应的对应的特征向量特征向量 归一化归一化 得到这七个网站的得到这七个网站的PRPR值：值： 利用线性代数的知识不难算得 0.70 0.38 0.32 0.24 0.41 0.10 0 = .14 0.30 0.17 0.14 0.11 0.18 0.05 0.06 三三. . 计算实例计算实例 第四步：考虑随机跳转时，使用迭代公式计算第四步：考虑随机跳转时，使用迭代公式计算 得到稳定的各网得到稳定
15、的各网页页的的PRPR值：值： 10 (1) nn dAd 通过设定一个极小的阈值，反复迭代直到上一次的PR值 与下一次的PR值差值小于该阈值即可终止迭代。 计算结果收敛于为： 1/70.290.28 1/70.150.16 1/70.120.14 1/70.080.11 1/70.270.18 1/70.050.06 1/70.050.07 三三. . 计算实例计算实例 迭代收敛速度问题 特征向量的求解，就是求解方程， 通常采用迭代求解方法，收敛速度很慢。 四四. PageRank. PageRank总结总结 假设 N 是 104、105或106的量级。采用 双精度记录，一个N 阶方阵 A
16、的存储量 为 分别为 800MB、80GB、8TB。目前， Google处理着80亿以上的页面，很显然， 已知的这种做法已经完全不适用了。 A= 计算机存储容量限制 G=0 0 0 1 0 1;1 0 0 0 0 0; 0 1 0 0 0 0 ;0 1 1 0 0 0;0 0 1 0 0 0;0 0 1 0 1 0;%邻接矩阵 p=0.85;%阻尼系数 d=sum(G); n,n=size(G); D=diag(1./d); %生成对角向量 e=ones(n,1);%全1的行向量 z=zeros(n,1); A=p*G*D+(1-p)./n*e*e; delta=0.0001; x=rand(n,1);%设置初始值为随机数 while max(abs(x-z)delta z=x; x=A*x; end x
黑公网安备:91230400333293403D