《华东师范大学 matlab exp09w》由会员分享，可在线阅读，更多相关《华东师范大学 matlab exp09w（34页珍藏版）》请在金锄头文库上搜索。
1、实验九 网站排名问题,数学实验,网站排名是网络搜索引擎的核心,本实验主要介绍 PageRank 算法，以及如何使用该算法对网站进行排名,问题背景和实验目的,PageRank 是著名网络搜索引擎 Google 用于评测一个网页 “重要性” 或 “影响力” 的一种方法,PageRank 算法中使用的数学知识包括：正矩阵性质、特征值和特征向量、幂迭代算法、Gauss-Seidel迭代算法等,PageRank 是 Google 用于评价一个网页的重要性的一种方法。通过该方法，Google 将各个网站进行排名。用户进行相关搜索时，Google 会将符合条件的网站按排名顺序输出。,PageRank 得分是
2、介于 0 和 10 之间的一个数，得分越大表示网页越重要。,可以下载Google的toolbar（约660K），安装后就可以显示所浏览的网页的PageRank得分。,http:/ 介绍,有向图的定义、相关术语和部分性质,例：右图为一个有向图，记为 D，其顶点组成的集合记为 V(D)=u,v,w 其有序数对组成的弧集记为 A(D)=(u,w),(w,u),(u,v),实验内容,有向图是指由有限个元素的非空集合和它的不同元素构成的有序数对组成的结构。,注：(u,w) 和 (w,u)表示不同的弧。,有向图 D 的顶点集的基数称为 D 的阶，记作 p(D) 有向图 D 的弧集的基数称为 D 的大小，记
3、作 q(D) (u,v)是有向图 D 的一条弧，称之为从 u 邻接到 v，而 v 是从 u 邻接的 有向图 D 的顶点 v 的出度(out-degree)是指 D 中从 v 邻接的顶点的个数，或以 v 为起点的弧的条数，记作 od(v) 有向图 D 的顶点 v 的入度(in-degree)是指 D 中邻接到 v 的顶点的个数，或以 v 为终点的弧的条数，记作 id(v),有向图相关术语,例1：右下图为一个有向图，记为 D，则,p(D)=3,D 的阶:,D 的大小:,顶点 u 的出度:,顶点 u 的入度:,顶点 v 的出度:,顶点 v 的入度:,q(D)=3,od(u)=2,id(u)=1,od
4、(v)=0,id(v)=1,有向图举例,p(D)=6，q(D)=9,例 2：左图中,有向图举例,为研究需要，我们定义邻接矩阵,对于例 2 中的有向图，其邻接矩阵为,邻接矩阵,性质一：定义行和 和列和 ，易知：第 i 行的行和 ri 就是第 i 个顶点的入度，第 j 列的列和 nj 就是第 j 个顶点的出度。,性质二： ，即他们都等于有向图 D 的大小（弧的个数）。,邻接矩阵的性质,行和 入度，列和 出度,Google 的 PageRank 是基于这样一个理论：若 B 网页上有连接到 A 网页的链接 ( 称 B 为 A 的导入链接 )，说明 B 认为 A 有链接价值，是一个“重要”的网页。当 B
5、 网页级别 ( 重要性 ) 比较高时，则 A 网页可从 B 网页这个导入链接分得一定的级别 ( 重要性 )，并平均分配给 A 网页上的所有导出链接,导入链接（也叫逆向链接）是指链接到你网站的站点，也就是我们一般所说的“外部链接”。而当你的网站上有链接指向另外一个站点时，这个站点就是你的“导出链接”。,在PageRank算法中，一个网页的级别（重要性）大致由下面两个因素决定：该网页的导入链接的数量和这些导入链接的级别（重要性）。,PageRank 的决定因素,如果我们将下面的有向图中的每个顶点看成一个网页，并把每个弧看成是网页间的 “超级链接”，则此有向图就代表一个小型的网络，其中有 6 个网页
6、和 9 个超级链接。,问：这 6 个网页中哪个最重要？,重要性的决定因素： 导入链接的数量 导入链接的重要性,看谁的导入链接多？,不太合理,哪个网页最重要,设 u 是某个网页，其级别（重要性）为 r(u)，记 Fu 为 u 的导出链接的集合， Bu 为 u 的导入链接的集合， nu =|Fu | 即是 u 的导出链接总数。,设 v 是 u 的一个导入链接，根据 PageRank 理论，u 从 v 处分得的级别（重要性）为 r(v)/nv 。将 u 从所有导入链接处分得的重要性相加，即为网页 u 的最终级别,简化的 PageRank 算法,设共有 m 个网页，分别编号为 1、2、3、.、m，它们
7、的级别（重要性）分别记为 r1、r2、r3、.、rm，G 表示由这些网页组成的有向图的邻接矩阵。根据有向图理论：,简化 PageRank 的数学模型,易知 r 是 Gm 的对应于特征值为 1 的特征向量,矩阵 Gm 一定有特征值 1 吗？即上面的方程是否有解？,如果 ，则 r1 = r2 ，此时就无法进行排名,因此，我们需要对简化的 PageRank 进行改进！,简化 PageRank 存在的问题,设 (u) 是网页 u 的所获得的基本级别，则,改进的 PageRank,基本思想：首先给每个网页设置一个基本级别,(u)= (1 p )/m ,矩阵 形式,与前面的讨论相类似，将所有网页进行编号：
8、 1、2、. 、m,改进的 PageRank,于是可以把右式改写为：,改进的 PageRank,其中：,规定：,记,x 是 A 的对应于特征 值 =1 的特征向量。,改进的 PageRank,改进的 PageRank,矩阵 A 的两个重要性质：,A0，即所有元素都是正数 A 的各列的列和等于 1, = (1 p )/m,若矩阵 A 中存在 0 行，即存在 j 使得对所有的 i 有 gij = 0，则将导致 nj = 0 ， 此时规定：,改进的 PageRank,问：上述方程组的解是否存在？,答：上述方程组的解存在且唯一！,理由：Perron-Frobnius 定理,x 满足：,改进的 Page
9、Rank,如果 A 是正的方阵（所有元素均大于0），则,Perron-Frobnius 定理,A 的谱半径 (A)0，其中 ， 1, 2, . , n 为 A 的特征值。 = (A) 是 A 的特征值，且代数重数为 1，即为单特征值。 存在唯一的 x 0，满足 A x = (A) x，且 若 是 A 的特征值，且 (A)，则 | (A) 。, = 1 是 A 的特征值吗？,A 的谱半径,A 的各列的列和等于 1,A 的行向量线性相关, = 1 是 A 的特征值,事实上，我们还有 (A)=1,例：用改进的 PageRank 算法计算下面的小型网络中各网页的排名，其中取 p=0.85。,网页排名举
10、例,clear; % fulu1.m p=0.85; % 此处 p 也可以取其它数值 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; n,n=size(G); D=sum(G); % 提取每列的列和 D=1./D; D=diag(D); % 生成对角矩阵 delta=(1-p)/n; A=p*G*D + delta; v,d=eig(A); % 计算 A 的特征值与特征向量 r=v(:,1); r=r./sum(r); x,rank=sort(r); x=flipud(x); r
11、ank=flipud(rank); . . % 输出结果,网页排名举例,幂迭代方法,当矩阵 A 的阶数很大时，无法直接计算其特征值和特征向量，此时需要使用迭代算法。,x = A x ，x 满足：,Power Iteration,Power Iteration,幂迭代方法具体计算步骤,输入矩阵 A 和迭代初始向量 v，以及精度 ，令 k = 0； 计算：vk+1 = Avk ； 如果 |vk+1 - vk | ，则计算 PageRank 级别并停机 。否则转第二步。,Power Iteration,例：采用幂迭代法计算下面各网页的排名，其中 p=0.85。,幂迭代法举例,clear; % ful
12、u2.m p=0.85; 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; n,n=size(G); sn=sum(G); % 提取每列的列和 D=diag(1./D); delta=(1-p)/n; A=p*G*D + delta; x=ones(n,1)/n; % 迭代初始向量 z=zeros(n,1); cnt=0; % 用于记录迭步数 while max(abs(x-z) 0.0001 % 设置精度 z = x; x = A*x; cnt=cnt+1; end x1,ran
13、k=sort(x); x1=flipud(x1); rank=flipud(rank); . . % 输出结果,幂迭代法举例,在前面给出的程序中，如果矩阵 G 中存在某一列的列和为零，怎么办？,如何在程序中体现上面的思想？ 一个修改后的 Matlab 程序（fulu3.m）,其实 fulu3.m 仍有问题，你能找出来吗？,一个彻底的解决方案见 Moler 编写的M文件，（参见fulu4.m），它充分利用稀疏矩阵的性质，当矩阵规模较大时，能大大减少运算量。,一个问题,此时规定：,计算与哈佛大学主页相关的 500 个网站的排名,下载 ncm.zip，解压到某个目录，并进入该目录,应用实例, loa
14、d harvard500 spy(G) x,cnt=pagerankpow(G) pagerank(U,G),装载与哈佛大学主页相关的 500 个网站的邻接矩阵 G，以及这500 个网站的地址和名称矩阵 U,查看稀疏矩阵 G 的形状,用幂迭代法计算这 500 个网站的 PageRank 级别向量 x，同时输出迭代次数,按 PageRank 级别大小输出级别大于 0.005 的网站,教材第 136 页，练习 7,clear; U,G=surfer(http:/,500); % 生成与华师大主页相关的500个站点的邻接矩阵， % 并保留这些站点名 pagerank(U,G); % 排名,应用实例,教材 P 136：练习 2、3、4、6,上机作业,写入实验报告册,将结果都输出到指定文件中,练习 1 自己上机练习，不用写入报告。,
