实验九-网站排名问题.pptVIP

数学实验 实验九 网站排名问题 问题背景和实验目的 PageRank 介绍 实验内容 有向图相关术语 有向图举例 有向图举例 邻接矩阵 邻接矩阵的性质 PageRank 的决定因素 哪个网页最重要 简化的 PageRank 算法 简化 PageRank 的数学模型 简化 PageRank 存在的问题 改进的 PageRank 改进的 PageRank 改进的 PageRank 改进的 PageRank 改进的 PageRank 改进的 PageRank 改进的 PageRank Perron-Frobnius 定理 A 的谱半径 网页排名举例 网页排名举例 x = 0.2675 0.2524 0.1697 0.1323 0.115 0.0625 Power Iteration Power Iteration Power Iteration 幂迭代法举例 幂迭代法举例 x1 = 0.2675 0.2524 0.1698 0.1323 0.1156 0.0625 一个问题 应用实例 clear; % fulu2.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); D=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,rank]=sort(x); x1=flipud(x1); rank=flipud(rank); ... ... % 输出结果 rank = 1 2 4 3 6 5 * * 网站排名是网络有哪些信誉好的足球投注网站引擎的核心 本实验主要介绍 PageRank 算法，以及如何使用该算法对网站进行排名 PageRank 是著名网络有哪些信誉好的足球投注网站引擎 Google 用于评测一个网页 “重要性” 或 “影响力” 的一种方法 PageRank 算法中使用的数学知识包括：正矩阵性质、特征值和特征向量、幂迭代算法、Gauss-Seidel迭代算法等 PageRank 是 Google 用于评价一个网页的重要性的一种方法。通过该方法，Google 将各个网站进行排名。用户进行相关有哪些信誉好的足球投注网站时，Google 会将符合条件的网站按排名顺序输出。 PageRank 得分是介于 0 和 10 之间的一个数，得分越大表示网页越重要。 可以下载Google的toolbar（约660K），安装后就可以显示所浏览的网页的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 2 sigma 6 1 1 rho 5 1 2 delta 4 3 1 gamma 3 2 1 beta 2 1 2 alpha 1 出度 入度 顶点 序号 例 2：左图中 为研究需要，我们定义邻接矩阵 对于例 2 中的有向图，其邻接矩阵为 性质一：定