首先申明,本博文自原创,部分数据来源于网络。
在google的搜索结果中,PR值越高的网页排在越前面。
网页权重的算法有很多种,为何我唯独选择了page
rank来讨论,不仅因为它是Google搜索引擎采用的搜索结果排名算法之核心,且它把整个互联网当做一个整体来对待且最终依靠经典的数学模型精准地得到web上网页的权重。
虽然今天的搜索引擎的排名系统远远要比这个算法复杂。域名数据,内容质量,用户数据,建站时间等都可能被考虑进去,但是page
rank算法仍然是核心的技术之一,使得Google名声大噪。关于page rank的介绍性文章,在Google黑板报里的” 谈 Page Rank
– Google
的民主表决式网页排名技术”。关于其更详细的论述,可以参照Google 的两个创始人拉里•佩奇 (Larry Page )和谢尔盖•布林 (Sergey Brin)的论文”The PageRank Citation Ranking: Bringing Order to the
Web”。
首先,page
rank基于以下的假设:”一个网页被引用 (即反向链接)的次数越多,则说明越重要;
一个网页虽然没有被多次引用,但是被重要的网页引用,则它也可能是很重要的;一个网页的重要性被平均的传递到它所引用的网页。”所以,为了说明问题的方便,就引出了下面这个简化了的Page Rank算法。简化版一:R(u) = cR(1)/N(1) +
……+cR(v)/N(v)。(v∈Bu)。其中R(v)是网页v的PR值,N(v)是网页v的正向链接数,B(u)是页面u的反向链接的集合。c是阻尼系数(Damping
Factor),它的值在0到1之间。因此,阻尼系数的使用,减少了其它页面对当前页面A的排序贡献。那么这个式子如何用数学的方法解答呢?首先可以认为整个互联网是一个大的有向图G=(V,E)。V是所有页面的集合,E是有向边的集合,(i,j)表示页i有指向页j的超链接。由于有向图和矩阵在本质上是可以互相转换的,下面举例是如何互转的:
此有向连通图模拟网页间的超链接
链接源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
如果我们假设Aij=1
,if (从页面 i 向页面 j 「有 」 链接的情况)
;Aij=0, if (从页面 i 向页面 j
「没有」链接的情况) 。则根据以上我们可以构造如下矩阵
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;
]
接下来再来看看公式一中的PR值求法,即
PR(1) = c[1*PR(2) + (1/2)*PR(3)
+ (1/4)*PR(5) +(1/2)*PR(6)];
PR(2) = c[(1/5)*PR(1) +
(1/2)*PR(3) + 0.25*PR(5) + 0.5*PR(5)];
............
PR(7) = c[(1/5)*PR(1) + 0+
0......];
则,可以得出PT =
cMPT,其中M的方阵如下,
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;
]
所以,PT为M的特征根为c的特征向量。只需求出最大特征根的特征向量,就是网页集对应的最终PageRank值,这可以用迭代方法计算。如何迭代呢?如果我们给定初始向量PT1’做第一次迭代,就相当于用初始向量乘以上面的矩阵。第二次迭代就相当于用第一迭代的结果再乘以上面的矩阵……实际上,在随机过程的理论中,上述矩阵被称为“转移概率矩阵”。这种离散状态按照离散时间的随机转移过程称为马尔可夫链(Markov
chain)。设转移概率矩阵为P,若存在正整数N,使得PN>0(每一个元素大于0),这种链被称作正则链,它存在唯一的极限状态概率,并且与初始状态无关。这篇”Google搜索与Inter网中的数学”文章里,描述了马氏链与page
rank的关系。
最后可以看到,从最开始的矩阵A到矩阵M可以很容易转化得到(将A倒置后将各个数值除以各自的非零要素)。
现在考虑有一个页面(比如是页面7),它不含有任何的超链接,即它的前向链接或者说出度为0,很显然,方阵M的最后一行为全零,这样,特征向量PT也为全零。我们也可以从图论的角度来阐述这个问题。我们可以这样定义一个有向图:图G的顶点集合为V={V1,V2,…,Vn},边的集合为E={Eij}。我们把有向图G的每个顶点都给定一个权值P(Vi),即为它的PR值。有向边AB的权值定义为A为B贡献的PageRank,也即网站A链接到网站B的概率。这样,对于一个顶点,若它的出度大于0,则从它出去的权值和为1(这一点可以从上述的方阵M中的列可以看出,满足了全概率)。显然,如果图中有一个顶点X的出度是0,那么经过有限次迭代后所有顶点的PR值都将变为0。这是因为由于X不对外贡献任何PR,所以整体的PR总和在不断减少,最终减为0。这个被拉里•佩奇和谢尔盖•布林称为rank
sink。为了克服这个问题,就有了下面这个公式:Rank算法简化版二:R(u) = (1-c)+
cR(1)/N(1) +
……+cR(v)/N(v)。(v∈Bu)。 ……公式二
(1-c)实际上为了服从概率分布。这样可以推导出P = (1-c)e +
cMP,即
P = [(1-c)eeT/n + cM]P
(eTP=n)。关于用矩阵方法来推导的更详细的文章,可以参考这篇"The $25,000,000,000
Eigenvector: The Linear Algebra Behind Google".
现在可以想象一下整个web中有250亿不止的网页,收敛速度是至关重要的。所以为什么作者拉里•佩奇 (Larry Page )和谢尔盖•布林 (Sergey Brin)要取c为0.85,在这篇文章”How Google Finds Your Needle in the
Web's Haystack”的最后部分讨论到。
Pagerank算法除了对搜索结果进行排序外,还可以应用到其它方面,如估算网络流量,向后链接的预测器,为用户导航等。这篇文章PageRank
sculpting.讲述了当前Google的一些改进.
后记,2001年9月,PageRank被授予美国专利,专利被正式颁发给斯坦福大学,佩奇作为发明人列于文件中。最后要说的一点,分析PR算法,用到了离散数学,线性代数,概率论,数值计算甚至随机过程,所以看来数学确实很好很强大需要认真学习啊。
|
相关推荐
Google page rank 算法经典论文,线性代数经典运用
page rank介绍,可以快速对page rank有初步的了解,明白google是怎么rank的(当然rank策略不限于pagerank)
1.google's page rank and beyond2.Understanding search engines附带阅读器,欢迎搜索爱好者和我联系交流,email:gigglesun@163.com.
ASP.NET百度权重,alexa排名,google page rank,google收录,百度收录和百度快照查询源代码.rar
主要讲解了pagerank算法,有兴趣的同学可以看一下,我觉得还不错
The first page Google rankings is what this eBook will strive to provide for you and it will offer you with hidden Google secrets which can help your web site or pages to rank well on search results....
此方法用于C# winform 获取指定页面的google pagerank值,绝对正确
pagerank matlab代码Google-PageRank 使用 Matlab 计算网络的 Google Page-rank。 如果你有类似的作业,请不要复制代码,试着理解它。
PaRaMeter stands for "Page Rank Meter" - a free Google PageRank checking and monitoring tool. PageRank is one of the methods Google uses to determine how relevant and important a page is. PageRank is ...
该项目是一个简单的Qt库扩展,用于检索任何公共网页的Google页面排名。 您可以异步使用库功能,这意味着您可以发送请求,稍后再收到一条带有答案的消息,您可以继续执行其他工作。 该项目还包括一个命令行工具,用于...
工具特色:支持同时查询Google PageRank/Sogou PageRank,支持URL伪静态,简单灵活方便配置。
语言:English ...获取Google Page Rank值,并仅在可用时将其显示在地址栏中。 多个图标集。 简单的。 最近的更改=============显示不可用图标的选项。 选择图标集的选项。 实现了改进的缓存。 更新了图标!
动摘要提取过程所提出来的,主要是借鉴Google公司Page-Rank算法的思路,将句子间的相似关系看成是一种推荐或投票关系,由此构建 TextRank 网络图
googles[1].pagerank.and.beyond_langville.meyer googles[1].pagerank.and.beyond_langville.meyer
#Google Chrome - Google 网页排名获取页面排名并将其显示在地址栏中的 Chrome 扩展程序安装位置: :
获取Google Page Rank值,并只有当这个值可用时才显示在地址栏中。多个图标集。简单。 近期变动 ============= 选项显示不可用的图标。 选择图标设置。 实现改进的缓存。 更新图标! 支持语言:English
但是,除了分别观察每个漏洞的风险因素之外,我们还采用与Google Page Rank Algorithm类似的方法引入了在特定时间对漏洞进行排名的概念。 使用具有三个记录的漏洞及其CVSS分数的计算机网络的简单模型来举例说明新的...
Google会为每个网站提供Pagerank(介于0到10之间)。 Pagerank是搜索引擎排名中的重要因素之一。GooglePagerank基于指向网站的高质量反向链接的数量。
PageRank 可以定义在任意有向图上,而与之类似的问题都可以用此模型,因而被应用到社会影响力分析、文本摘要等多个问题,成了越来越被关注的经典算法。 本资源:本资源利用python资源,进行网络图生成,按照...
网页排名 发射 python random_algo.py将创建pagerank随机行者的随机gif 随机性 Pagerank算法中有两件事... 必须选择它以产生不可约的过渡矩阵(请参阅google_matrix下的注释)。 悬空指令与个性化指令相同是很常见的。