重点不是说PageRank是什么,而是怎么用代码实现
什么是PageRank?PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由[1] 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。
PageRank的诞生背景?早期的搜索引擎经历了“不评价” 和“基于检索词”的评价两个阶段。 “基于检索词”的评价算法很直观,但是容易受到“Term Spam”的攻击。其实从搜索引擎出现的那天起,spammer和搜索引擎反作弊的斗法就没有停止过。Spammer是这样一群人——试图通过搜索引擎算法的漏洞来提高目标页面(通常是一些广告页面或垃圾页面)的重要性,使目标页面在搜索结果中排名靠前。用户很容易被带入垃圾网页,用户体验极差。PageRank也应运而生。
怎么实现PageRank?简单的说PageRank让链接来"投票",一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。
最简单pagerank模型网页,可以抽象成的图当中的结点,网页与网页当中的链接关系可以模型化为数据结构中逻辑结构图再具体点是有向图(表示哪个网页链接哪个网页),我们可以把链接关系用作离散数学图论当中的可达矩阵形象具体的表示,下面我来给大家具体的说明,如下面这个例子:
这个例子中有四个网页,如果当前在A网页,那么上网者将会各有1/3的概率浏览到B、C、D网页,这里的3表示A有3条出链,如果一个网页有k条出链,那么跳转任意一个出链上的概率是1/k,同理D到B的概率1,而B到C的概率为1。一般用转移矩阵表示上网者的跳转概率,如果用n表示网页的数目,则转移矩阵M是一个n*n的方阵(可由可达矩阵转换成转移矩阵);如果网页j有k个出链,那么对每一个出链指向的网页i,有M[i][j]=1/k,而其他网页的M[i][j]=0;上面示例图对应的可达矩阵如下:
A B C D
A 0 1 0 0
B 1 0 0 1
C 1 1 0 0
D 1 0 1 0
对应的转移矩阵为:
A B C D
A 0 0.5 0 0
B 0.33 0 0 1
C 0.33 0.5 0 0
D 0,33 0 1 0