PageRank算法核心思想及数学支撑

佩奇排名(PageRank),又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。[来该段自于Wikipedia对PageRank的权威诠释]

自从Google在商业上获得巨大成功后,它大力推行的PageRank也成为企业界和学术界十分关注的计算模型。Google将糅合入Title标识、Keywords关键字标识等因素的PageRank结果来调整搜索结果,使得“更加重要/等级更高”的网站呈现在检索结果中,从而提高搜索结果的相关度、质量。PageRank的结果从0到10,10级为满分。PR值越高说明网页越重要/受欢迎。例如PR值为1的网站不太重要,而PR值为7~10的网站可以说是非常重要了。一般到4,就能说是一个不错的网站。Google将自身PR值定为10.


在PageRank算法之前,曾经有人提出利用网页的入链数量作为依据进行链接分析,即认为入链越多,则该网页重要度越高。早期搜索引擎也采用该方法作为搜索引擎检索方法,对于检索结果亦起到较明显提升。而PageRank不单考虑到入链数量,也考虑到网页质量因素,两者结合后网页重要性评价则更为准确。

1、基本思想:

即对于某个网页A而言,该网页PageRank值的计算基于以下两个假设:

1:数量假设,如果越多的网页指向A,即A的入链数量越多,则该网页越重要;

2:质量假设,如果指向A的网页质量越高,则A越重要,即权重因素不同。

现实中一个具体的假设案例是:一篇论文被诺贝尔奖得主所引用, 显然要比被普通研究者所引用更说明其价值;一篇论文被100位学者引用,显然要比只有一位普通学者引用之更有价值。

初始阶段,网页通过链接关系构建起Web图,每个页面设置相同的PageRank值(原因在稍后阐述),通过若干轮的计算,会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行,网页当前的PageRank值会不断得到更新。

在每一轮更新页面PageRank得分的计算中,每个页面将其当前的PageRank值平均分配到本页面包含的出链上,这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和,即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值,就完成了一轮PageRank计算。

用公式来表示,若网页T存在一个指向网页A的链接,则表明T的所有者认为A是重要的,从而把T的一部分重要性得分赋予A。

这个重要性得分值为:PR(T)/C(T) ,其中PR(T)为T的PageRank值,C(T)为T的出链数。

对于A而言,A的PageRank值为一系列类似于T的页面重要性得分总和。一个页面的PageRank是由所有链向它的页面(链入页面)的重要性经过递归算法得到的。

2、PageRank的简单计算


3、PageRank的修正公式

现实网络中,由于存在出链度数为0,即不链接到任何网页的页面,但是很多网页可以访问它。鉴于这类情况,PageRank公式需要进行修正,修正的方法是,在简单公式的基础上增加阻尼系数d(damping factor):

该公式是计算网页A的PR值公式。Ti是存在到A的链接的网页。C(Ti)是网页Ti中存在的链接的数量。d是阻尼系数,一般定义为用户随机点击链接的概率,根据工程经验一般取0.85。而(1-d)代表着不考虑入站链接的情况下随机进入一个页面的概率。

还有一种修正方式与第一种相似,公式如下:


其中p(i)是第i个页面,N是页面总数,q是阻尼系数,(1-q)代表着不考虑入站链接的情况下随机进入一个页面的概率,L(pi)是Pi链出页面的数量。所有页面的PageRank值可以组成一个特征向量,这个特征向量矩阵为:


R是如下矩阵方程式的一个解:

其中 L(Pi,Pj) 表示网页 j 指向网页 i 的链路权重,并且若网页i存在指向网页j的一个链接,则


否则,L(Pi,Pj) = 0.

关于R矩阵方程式的含义,按照矩阵相乘规则,实际上是所有网页节点的方程式聚合组:

以第一行为例,分拆开来实际上是:

PR(P1) = (1-q)/N + a*(L(p1,p1)*PR(P1) + L(p1,p2)*PR(P2) + ... + L(p1,pn)*PR(Pn) )

其余行数以此类推。遂构成上述矩阵方程式。

到现在为止,我们把PageRank的计算方式和原理都阐述了,但是仍然有一个问题:先有鸡还是先有蛋?我们要知道一个网页 Wi的排序, 不仅要知道有多少网页链接了它, 而且还得知道那些网页各自的排序——因为来自排序靠前网页的链接更有分量。 而但作为互联网大家庭的一员, Wi本身对其它网页的排序也是有贡献的, 而且基于来自排序靠前网页的链接更有分量的原则, 这种贡献与 Wi本身的排序也有关。简而言之,链接到Wi的网页们影响了Wi的重要性排名,而Wi也有可能反向影响其余网页的排名,想要知道其余网页的排名,那么首先又要知道Wi的排名。这就是先有鸡还是先有蛋的意思。

为了打破这个死循环,佩奇和布林采用了一个奇妙的思路,分析一个虚拟用户在互联网的漫游过程。他们做了这样的假定:该虚拟用户访问了一个网页后,下一步将有相同的几率访问被该网页链接的任何一个其他网页。初看之下这一假设不合情理,用户都会存在自己的偏好,不可能以相同几率访问一个网页所有链接。但是在PageRank中,考虑到我们这一虚拟用户实际上是对所有互联网漫游者所做的平均意义上的代表,这样一来这条假设就不像初看之下那么不合理了。实际上就也是PR(T)/C(T) 的来源。最终的网页排序,则由用户在网络上漫游了很长时间---理论上是无限时间后---访问各网页的几率分布来决定,访问几率越大的网页排序则越靠前。(细心的读者可以发现,在该核心思想下,网页排序与搜索关键词并无关系!这意味着排序计算可以单独进行,而无需在用户输入keywords后再临时进行,这是Google搜索速度迅即的重要原因!)










所以综上,一个页面的PageRank值是由其他页面的PR值计算得到的。Google不断的重复计算每个页面的PR值。给每个页面一个初始的非零随机PR值,那么经过不断地迭代计算,最终每个页面的PR值将趋于稳定。这是PageRank的奇妙所在以及为何搜索引擎使用它的原因。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 151,511评论 1 330
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 64,495评论 1 273
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 101,595评论 0 225
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 42,558评论 0 190
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 50,715评论 3 270
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 39,672评论 1 192
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 31,112评论 2 291
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 29,837评论 0 181
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 33,417评论 0 228
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 29,928评论 2 232
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 31,316评论 1 242
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 27,773评论 2 234
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 32,253评论 3 220
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 25,827评论 0 8
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 26,440评论 0 180
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 34,523评论 2 249
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 34,583评论 2 249

推荐阅读更多精彩内容