怎样求得 PageRank(2)

PageRank 的计算,就是求属于这个推移概率行列最大特性值的固有矢量(优固有矢量)。

这是因为,当线性变换系 t→∞ 渐近时,我们能够根据变换行列的"绝对价值最大的特性值"和"属于它的固有矢量"将其从根本上记述下来。换句话说,用推移概率行列表示的概率过程,是反复对这个行列进行乘法运算的一个过程,并且能够计算出前方状态的概率。

再者,虽然听起来很难,但是求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值,但是因为不断地将行列相乘,得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量,把固有矢量中特征性的标量(scalar)称为特性值,把这样的计算方法总称为分解特性值,把解特性值的问题称为特性值问题。

(*注) 对 N 次的正方行列 A 把满足 Ax =λx 的数 λ 称为 A 的特性值,称 x 为属于 λ 的固有矢量。如果你怎么也不能适应行列的概念的话,你也可以考虑 N×N 的二元排列就可以了。同时,也可以把矢量考虑成为长度为 N 的普通的(一元)排列就可以了。

简单的例子
让我们用简单的例子来试着逐次计算 PageRank 。首先考虑一下有像下图表示那样的链接关系的7个HTML文件。并且,这些HTML文件间的链接关系只是闭合于这1-7的文件中。也就是说,除了这些文档以外没有其他任何链接的出入。另外请注意,所有的页面都有正向和反向链接(即没有终点),这也是后面将提出的一个重要假定,在此暂且不深入探讨。

表示页面间互相链接关系的推移图

首先,把这张推移图图表构造的邻接列表表示为排列式,就有以下式子。即,根据各个链接源ID列举链接目标的ID。

链接源I D  链接目标 ID
1  2,3 ,4,5, 7
2  1
3  1,2
4  2,3,5
5   1,3,4,6
6  1,5
7  5
以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 7×7 的正方行列。一个仅有要素 0 和 1 位图行列(bitmap matrix)。横向查看第 i 行表示从文件 i 正向链接的文件ID。

A = [
  0, 1, 1, 1, 1, 0, 1;
  1, 0, 0, 0, 0, 0, 0;
  1, 1, 0, 0, 0, 0, 0;
  0, 1, 1, 0, 1, 0, 0;
  1, 0, 1, 1, 0, 1, 0;
  1, 0, 0, 0, 1, 0, 0;
  0, 0, 0, 0, 1, 0, 0;
 ]
PageRank 式的推移概率行列 M ,是将 A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 7×7 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件ID(文件 i 的反向链接源)。请注意,各纵列的值相加的和为 1(全概率)。

M = [
 0,  1, 1/2, 0, 1/4, 1/2, 0;
 1/5, 0, 1/2, 1/3, 0, 0, 0;
 1/5, 0, 0, 1/3, 1/4, 0, 0;
 1/5, 0, 0, 0, 1/4, 0, 0;
 1/5, 0, 0, 1/3, 0, 1/2, 1;
 0, 0, 0, 0, 1/4, 0, 0;
 1/5, 0, 0, 0, 0, 0, 0;
]
表示 PageRank 的矢量 R (各个的页面的等级数的队列),存在着 R = cMR 的关系(c 为定量)。在这种情况下,R 相当于线形代数中的固有矢量,c 相当于对应特性值的倒数。为了求得 R ,只要对这个正方行列 M 作特性值分解就可以了。

在分解特性值时有相应的各种各样的数值分析法,但是本文将不在这里对各种方法详细说明,请读者自己去阅读一本恰当的教科书(在你的暑假里一定有这么一本被埋没的教科书)。在此,我们就暂且使用决 GNU Octave 这个计算程序实际计算一下特性值和固有矢量。

(*注) GNU Octave ,是支持数值计算,类似于描述性出色的 MATLAB 的编程语言。扩展后的处理语言更适合于行列演算,但基本上和C语言的语风相像,因此可读性很高。当然,除了Octave以外 MATLAB 和 Scilab 也是非常不错的语言,但是根据 GPL, Octave 是最容易得到的。

时间: 2024-10-01 04:30:17

怎样求得 PageRank(2)的相关文章

怎样求得 PageRank(3)

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 实际举例下面我们举一个实际例子.如果不太明白以下例子在做什么的话,只要认为我们能够使用 Octave 这个程序来解特性值问题即可. 首先,使用恰当的编辑器制作以下 Octave 脚本.(在行尾加上分号就能消去多余的结果输出,不过,此次为了说明特意去掉了.) % cat pagerank.m #!/usr/bin/octave ## pager

PageRank 专题

Google 的秘密- PageRank 彻底解说本文对作为评价甚高的搜索引擎 Google    的核心技术之一 PageRank (网页等级)的基本的概念和评价原理进行解释.索引前言 PageRank 的基本概念 怎样求得 PageRank 实际应用时的问题 Namazu 上的实际安装实验 对 PageRank 的个人见解 参考文献 附录:「guguru?/gouguru?」 ★(2003/7/1) 拙著『Namazu系统的构筑和活用』已作修订. 详情请看 介绍页面 .★(2003/5/20

Google Pagerank,中国站长自欺欺人的游戏

仅以此文献给在PR上挣扎的站长们 google拥有世界上领先的搜索引擎技术,他们有最大的资金后盾,有最强的技术团队,有着别的公司无法比拟的公司文化底蕴.google全球最大的搜索引擎,搜索引擎界的大哥大. 一连串的头衔把google这个巨人几乎捧到了天顶上了,它现在在个人站长眼中就像神明一样,它每一次的变动都能牵动站长们的心,每一个新政策的推出都受到了巨大的关注.如果你是个人站长你肯定访问过www.google.com/webmaster这个页面,你肯定会使用它提供的每一个工具,并且这些工具是那

【原创】机器学习之PageRank算法应用与C#实现(1)算法介绍

考虑到知识的复杂性,连续性,将本算法及应用分为3篇文章,请关注,将在本月逐步发表. 1.机器学习之PageRank算法应用与C#实现(1)算法介绍 2.机器学习之PageRank算法应用与C#实现(2)球队排名应用与C#代码 3.机器学习之PageRank算法应用与C#实现(3)球队实力排名应用与C#代码  Pagerank是Google排名运算法则(排名公式)的一部分,是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准.在揉合了诸如Title

论页面等级(PageRank)是否存在渗漏损失问题

是否存在|问题|页面    论页面等级(PageRank)是否存在渗漏损失问题  如果你已经读过了"Google专利网页级别技术PageRank揭密"或Google的PageRank技术说明,也许你会对我在这篇文章中将要谈论的这个问题表示认可. 为什么我会提出这样一个奇怪的问题?其实并不奇怪,因为这个问题已逐渐变成人们注意的焦点并开始给大家带来困扰.有些人说根本不存在这样的问题,有些人则更加认为这只是个荒诞的说法.-页面等级是否存在漏损的问题?如果是,这种损失有多严重?--我认为是对这

Google降低PageRank惩罚付费链接

Google很早就声称要惩罚以SEO(搜索引擎优化)为目的的付费链接,这些天已经开刀了,我经常访问的好几个国外知名的Blog都中了招,PageRank被Google降低到4甚至3. 据Zac的报道,被Google惩罚的网站包括: washingtonpost.com/ PR7 to PR5 statcounter.com/ PR10 to PR6 autoblog.com/ PR6 to PR4 engadget.com/ PR7 to PR5 problogger.net/ PR6 to PR

Google PageRank数字背后的含意

Google PageRank是Goog le给网页的计分机制,透过这个机制Google就能决定哪个网页可能比较重要, 比较是人们想要找的. 官方给予的说法是: 以下为引用的内容:PageRank 如同个别网页价值的指示器, 透过庞大的连结架构来信赖网站独特地民主性质. 简单来说,Google 说明网页 A 连结至网页 B 时,则视为网页 A 投给网页 B 一票. 当然,Google 会查看票数来源,或是连结网页接收的票数: 同时它也会分析参予投票的网页. 透过「重要的」网页来参予投票,并且帮助

Google工具条要跟PageRank说再见?

最先提出Google应该去掉PR值显示的Tedster认为:Google 早已将PageRank对搜索引擎的重要程度一降再降,过期时间长达三至四个月之久的PR值不仅不会体现出一个网站的真正价值,反而会造成一些混乱现象: PR低的网站不会受到广告主的青睐.付费链接购买PR等让Google头疼的问题,所以现在是时候叫Google取消显示工具列上的PR值了. 大家对Google PageRank的关注度日渐降低,不过像我一样从来没有过PR的人还是挺希望拥有一个绿绿的条,按道理说,现在正是Google

教你在Google PageRank值更新前预测自己的新PR

GooglePR值将于近日更新,这是每一个关心自己网站在Google谷歌搜索结果页排名情况的人今日关注的焦点,当然,关于GooglePR值的新闻也多了起来. 其实有一个办法可以提前知道你的PR值,至少是作为参考,并且八九不离十,那就是Sogou Rank值,相比较GooglePR值,Sogou Rank值每周更新,更新速度更快,但是也有一个缺点,那就是Sogou Rank只索引国内的网站,如果你的博客在国外也有巨大的影响力的话,Sogou Rank值与Google PR值就会有些差异. 拿几个例