第三讲矩阵特征值计算.pptxVIP

第三讲 矩阵特征值计算 —— 应用：Google 网页排名 2 网站排名是网络有哪些信誉好的足球投注网站引擎的核心 本讲主要介绍 PageRank 算法的基本思想与模型，以及如何使用该算法对网站进行排名 PageRank PageRank 是著名网络有哪些信誉好的足球投注网站引擎 Google 用于评测一个网页 “重要性” 或 “影响力” 的一种方法。通过该方法，Google 将各个网站进行排名。用户进行相关有哪些信誉好的足球投注网站时，Google 会将符合条件的网站按排名顺序输出。 PageRank 算法中使用的数学知识包括：正矩阵性质、特征值和特征向量、幂迭代算法、Gauss-Seidel迭代算法等 PageRank 得分越大表示网页越重要。 3 有 向 图 4 有向图的定义、相关术语和部分性质 例：右图为一个有向图，记为 D，其顶点组成的集合记为 V(D) = { u, v, w} 边组成的集合记为 A(D) = {(u,w), (w,u), (u,v)} 有向图介绍 有向图是指由有限个元素的非空集合和它的不同元素构成的有序数对组成的结构。 注：(u,w) 和 (w,u) 表示不同的边。 图的基本元素：顶点（节点）和边（线、弧、枝） 5 有向图 D 的顶点集的基数称为 D 的阶，记作 p(D) 边组成的集合的基数称为 D 的大小，记作 q(D) 顶点 v 的出度 (out-degree) 是指从 v 邻接的顶点的个数，或以 v 为起点的边的条数，记作 od(v) 顶点 v 的入度(in-degree)是指 D 中邻接到 v 的顶点的个数，或以 v 为终点的边的条数，记作 id(v) 有向图相关术语 6 例：右下图为一个有向图，记为 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 有向图举例 7 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 例：左图中 有向图举例 8 为研究需要，我们定义邻接矩阵 例：对于右边的有向图，其邻接矩阵为 邻接矩阵 9 邻接矩阵的性质 行和  入度，列和  出度 10 PageRank 数学模型 11 Google 的 PageRank 是基于这样一个理论： 若 B 网页上有连接到 A 网站的链接 ( 称 B 为 A 的导入链接 )，说明 B 认为 A 有链接价值，是一个“重要”的网站，此时 A网站可从 B网站分得一定的级别 ( 重要性 )。 同时 A 的级别将平均分配给 A网站上的所有导出链接。 导入链接：链接到你网站的站点，即“外部链接”； 导出链接：网站上指向另外一个站点的链接。 在 PageRank 模型中，一个网站的级别（重要性）大致由下面两个因素决定：导入链接的数量和导入链接的级别（重要性）。 PageRank 的决定因素 12 如果我们将下面的有向图中的每个顶点看成一个网站，并把每条边看成是网站间的 “超链接”，则此有向图就代表一个小型的网络，其中有 6 个网站和 9 个超链接。 例：这 6 个网站中哪个最重要？ 重要性的决定因素： 导入链接的数量 导入链接的重要性 看谁的导入链接多？ 不太合理 哪个网页最重要 13 设 u 是某个网页，其级别（重要性）为 r(u)，记 Fu 为 u 的导出链接的集合， Bu 为 u 的导入链接的集合， nu = |Fu | 即是 u 的导出链接总数。 设 v 是 u 的一个导入链接，根据 PageRank 理论，u 从 v 处分得的级别（重要性）为 r(v)/nv 。将 u 从所有导入链接处分得的重要性相加，即为网页 u 的最终级别 简化的 PageRank 算法 14 设共有 m 个网页，分别编号为 1、2、3、...、m，它们的级别（重要性）分别记为 r1、r2、r3、...、rm，G 表示由这些网页组成的有向图的邻接矩阵。根据有向图理论： 简化的PageRank模型 15 易知 r 是 Gm 的对应于特征值为 1 的特征向量 矩阵 Gm 一定有特征值 1 吗？即上面的方程是否有解？ 简化PageRank的问题 16 设 (u) 是网页 u 的所获得的基本级别，则 改进的 PageRank 基本思想：首先给每个网页设置一个基本级别 (u)= (1 – p )/m   17 矩阵 形式 与前面的讨论相类似，将所有网页进行编号： 1、2、... 、m 改进的 PageRank 于是可以把右式改写为： 18 改进