实验 网站排名问题资料.ppt

在前面给出的程序中，如果矩阵 G 中存在某一列的列和为零，怎么办？ 如何在程序中体现上面的思想？ 一个修改后的 Matlab 程序（fulu3.m） 其实 fulu3.m 仍有问题，你能找出来吗？ 一个彻底的解决方案见 Moler 编写的M文件，（参见fulu4.m），它充分利用稀疏矩阵的性质，当矩阵规模较大时，能大大减少运算量。 一个问题 此时规定： * 计算与哈佛大学主页相关的 500 个网站的排名 下载 ncm.zip，解压到某个目录，并进入该目录 应用实例 load 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(,500); % 生成与华师大主页相关的500个站点的邻接矩阵， % 并保留这些站点名 pagerank(U,G); % 排名 应用实例 * 教材 P 136：练习 2、3、4、6 上机作业 写入实验报告册 将结果都输出到指定文件中 练习 1 自己上机练习，不用写入报告。 * 实验九 网站排名问题 数学实验 网站排名是网络有哪些信誉好的足球投注网站引擎的核心 本实验主要介绍 PageRank 算法，以及如何使用该算法对网站进行排名 问题背景和实验目的 PageRank 是著名网络有哪些信誉好的足球投注网站引擎 Google 用于评测一个网页 “重要性” 或 “影响力” 的一种方法 PageRank 算法中使用的数学知识包括：正矩阵性质、特征值和特征向量、幂迭代算法、Gauss-Seidel迭代算法等 * PageRank 是 Google 用于评价一个网页的重要性的一种方法。通过该方法，Google 将各个网站进行排名。用户进行相关有哪些信誉好的足球投注网站时，Google 会将符合条件的网站按排名顺序输出。 PageRank 得分是介于 0 和 10 之间的一个数，得分越大表示网页越重要。 可以下载Google的toolbar（约660K），安装后就可以显示所浏览的网页的PageRank得分。 / PageRank 介绍 * 有向图的定义、相关术语和部分性质 例：右图为一个有向图，记为 D，其顶点组成的集合记为 V(D)={u,v,w} 其有序数对组成的弧集记为 A(D)={(u,w),(w,u),(u,v)} 实验内容 有向图是指由有限个元素的非空集合和它的不同元素构成的有序数对组成的结构。 注：(u,w) 和 (w,u)表示不同的弧。 * 有向图 D 的顶点集的基数称为 D 的阶，记作 p(D) 有向图 D 的弧集的基数称为 D 的大小，记作 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(v)=0 id(v)=1 有向图举例 * p(D)=6，q(D)=9 序号 顶点 入度 出度 1 alpha 2 1 2 beta 1 2 3 gamma 1 3 4 delta 2 1 5 rho 1 1 6 sigma 2 1 例 2：左图中 有向图举例 * 为研究需要，我们定义邻接矩阵 对于例 2 中的有向图，其邻接矩阵为 邻接矩阵 * 性质一：定义行和 和列和 ，易知：第 i 行的行和 ri 就是第 i 个顶点的入度，第 j 列的列和 nj 就是第 j 个顶点的出度。 性质二： ，即他们都等于有向图 D 的大小（弧的个数）。 邻接矩阵中元素为 1 的个数 邻接矩阵的性质 行和 ? 入度，列和 ? 出度 * Google 的 PageRank 是基于这样一个理论：若 B 网页上有连接到 A 网页的链接 ( 称 B 为 A 的导入链接