网页排序算法

1、网页排序算法PagerankHitsHilltopTrustRank硕0032班 3110082019 1Pagerankpagerank对网页的重要性进行客观的测定。PageRank 会将网页 A 上指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票，而不是计算直接的链接数。PageRank 也会考虑发出投票的每个网页的重要性，也就是某些网页的投票具有的价值较大，为该链接的页面赋予的价值因而也就较大。 重要的网页会得到较高的 PageRank，并出现在搜索结果的顶部。 Google 的技术是利用网络中的综合信息来确定网页的重要性。 因为没有人工干涉，也不对结果进行操纵，所以用户一直

2、信任 Google 是一个不会因付费而影响排名的客观信息来源。2PageRank的大小取决于三个因素：链入网页数链入网页的质量链入网页的链出网页数PageRank3PageRank的大小取决于三个因素：链入网页数链入网页的质量链入网页的链出网页数PageRank4矩阵表示页面的重要性由链向它的页面的重要性决定页面i的重要性 指向页面i的页面集页面j的出链页面j的重要性5计算PR(A)=(1-d) + d*(PR(T1)/C(T1)+ PR(Tn)/C(Tn)d: 阻尼系数, 通常设置为0.85.一个用户不用通过键入URL地址 ，而是点击链接的概率T1, , Tn: 指向页面A的页面集PR(A)

3、: 页面A的权威值.PR(Ti): 页面Ti的权威值.C(Ti): 页面Ti的出链.6Example of CalculationPage A 1Page C1Page B1Page D11*0.85/21*0.85/21*0.851*0.851*0.857Example of calculation经过20 次迭代：Page A 1.490Page C1.577Page B0.783Page D0.158Pagerank的问题PageRank算法中对于向外链接的权值贡献是平均的，不考虑不同链接的重要性。1.有些链接具有注释性，也有些链接是起导航或广告作用。有注释性的链接才用于权威判断。2.基

4、于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。9HitsHITS是英文Hyperlink-Induced Topic Search 的缩写意译为超链引导主题搜索。HITS 算法由Jon Kleinberg 于1997 年提出，并申请了专利。其基本思想是利用页面之间的引用链来挖掘隐含在其中的有用信息。具有计算简单且高效的特点。Hits算法认为对每一个页面应该将其内容权威度（authority)和链接权威度（hub）分开考虑，在对网页内容权威度做出评价的基础上再对页面链接权威度进行评价，然后给出该页面的综合评价。10hub和anthority链接权威度（hub）指的是页面上所有导

5、出链接指向页面的内容权威值之和。内容权威度（authority）指的是所有导入链接所在页面的链接权威度之和对于一个给定的查询，每个页面都被赋予了一个特定的链接权威度（hub）和内容权威度（authority）结果就是高权威度的页面11Hits算法过程HITS算法的求解过程如下：1、得出根集页面2、将所有页面（根集页面）的A和H赋予初值。3、计算新一轮的H和A的值。4、规范化结果5、重复3、4, 直到结果收敛。12根集页面将查询q提交给传统的基于关键字匹配的搜索引擎搜索引擎返回很多网页，从中取前n个网页作为根集(root set)，用S表示。S满足如下3个条件：1S中网页数量相对较小2S中网页大

6、多数是与查询q相关的网页3S中网页包含较多的权威网页。通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T(base set)13Hub和Authority的计算基集上的迭代算法: 内容权威值（authority weights ）a(p) 链接权威值（hub weights） h(p) 所有的网页初始化a(p) = 1，h(p) = 1重复下面两步并且规范化处理直到权威值收敛：。 14规范化处理15矩阵表示AMHii*1-=HMAiTi*1-=HMMHTii*1-=AMMAiTi*1-=16例子 Iteration 0 1 2 3 XYZX is the best hub i

7、s most authoritative17Hits 的问题HITS 算法的最大缺点是，它是在查询阶段进行计算，而不是在抓取或预处理阶段。以牺牲查询排名响应时间为代价的。不过HITS 算法的思想很可能融入到搜索引擎的索引阶段，也就是根据链接关系找出具有hub特征或authority特征的页面。HITS 算法还存在主题漂移的问题，如果在集合T中有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就偏离了原来的查询主题网页中一些无关的链接影响A，H值的计算18PageRank v.s. HitsPageRank 查询之前就计算了所有数据库中网页的权威值只计算权威值迭代计算量大，

8、计算速度快HITS 每次只检索跟查询有关的网页 计算两个值，内容权威值（authority）链接权威值（hub）计算简单，在线实时计算耗时多19HILLTOP算法HillTop ，是一项搜索引擎结果排序的专利，是Google的一个工程师Bharat在2001年获得的专利。Hilltop算法的指导思想和PageRank一致，都是通过网页被链接的数量和质量来确定搜索结果的排序权。但hilltop认为只计算来自具有相同主题的相关文档链接对于权重计算的贡献比主题不相关的链接价值要更高。Bharat称这种对主题有影响的文档为“专家”文档，从这些专家文档页面到目标文档页面的链接决定被链接网页的权重值20H

9、illtop算法步骤1.根据查询寻找“专家网页”。计算专家页面得分。2.给顶部专家网页链向的目标网页打分，这个过程综合了它与所有相关专家网页的链接关系基于“专家”文档的Hilltop算法最大的难点是第一次“专家文档”的筛选。目前Google首先给了.edu,.gov和.org站点很高的优先级。211.1专家页面的条件搜索引擎根据用户查询日志发现热门关键词后，开始针对这些热门关键词寻找专家页面成为专家页面的2个必要因素必须存在足够多而且不存在隶属关系的出链（检测k个出链的URL是否指向k个无从属关系的独立主机）至少存在一个短语包含该热门关键词的所有术语22从属关系两台主机,如果满足下列条件之一或

10、两者都满足,则这两台主机是有从属关系的:他们拥有相同的前3段IP地址主机名最右边的特殊标记相同.例如:比较和ibm.co.mx,分别忽略它们的类别后缀com”和co.mx,最右边得到的标记都是”ibm.因此它们被认为有从属关系.从属关系是具有传递性的:如果A和B有从属关系并且B和C也有从属关系,那么即使A和C没有明显的直接联系,也会被认为有从属关系231.2专家页面评分确定专家页面后，在该页面上找出所有包含热门关键词中术语或者差1到2个术语的短语将这些短语分为三个等级分。分别为全部包含S0、差1-S1、差2S2分别计算等级分这三个等级相差很大 依次为232 216和1而短语得分取决于这个短语在

11、页面中的位置，分数从高到低-标题 、头部、 锚文本等等等级分是对各个等级中所有短语得分的和。然后综合计算这三个等级得分就得到专家分更倾向于完全匹配24专家页面得分Expert_Score = 232 * S0 + 216 * S1 + S2Si = SUMkey phrases p with k - i query terms LevelScore(p) * FullnessFactor(p, q)LevelScore(p)是定义好的关键短语p的类型得分，在HillTop算法 中名称短语(title)的是16，标题(head)是6，锚文本(anchor)是1完整性因子FullnessFacto

12、r(p,q)是对q中关键词覆盖了p中关键词的数 量的度量。 设plen是P的长度，m是在p中而不在q中出现的术语的数量， FullnessFactor(p,q)的计算公式为：If m2, FullnessFactor(p,q)=1-(m-2)/plen252.1对目标页评分由排名前N个(至少两个)非隶属的专家页面指向的页面称为目标页面。目标页面的分数通过以下三步计算：1. 对每一个专家页面E指向目标页面T画边Edge(E,T)对每一个查询关键词w，设occ(w,T)是专家文档E中包含w且修饰Edge(E,T)的关键短语的数量。 If occ=0 Edgescore=0 else Edgesco

13、re=Expertscore* SUMquery keywords w occ(w，t)2.检查指向同一页面的专家页面的从属性，若存属性相同则删去minedgescore3.targetscore=sumedgescore26重要特征先计算一个与用户查询主题最相关的“专家文档”页面列表，然后通过专家页面找到目标页面，目标页面按照指向他们的非附属专家文档的数量和相关性进行排名若没有找到搜索引擎认为足够的“专家文档”（要求至少两个），则该算法失效即结果返回为零对于高度明确化的查询条件，此算法的结果很可能为027存在问题专家页面的搜索和确定对算法起关键作用；而其质量和公平难以保证Hilltop忽略了

14、大多数非专家页面的影响专家页面只占到整个页面的1.79%，不能全面反映民意Hilltop也是在线运行的，势必会影响查询响应时间，随着专家页面集合的增大，算法的可伸缩性存在不足之处28TrustRank算法TrustRank 是近年来比较受关注的基于链接关系的排名算法。TrustRank 中文可以翻译为信任指数。TrustRank 算法最初来自于2004 年斯坦福大学和雅虎的一项联合研究，用来检测垃圾网站，并且于2006 年申请专利。29TrustRank 算法核心思想网站TrustRank的计算采用人工和机器连接分析相结合的方式。通过Google或其他一些检索机构的专家，可以先确定一批站点的T

15、R值，在通过机器的连接结构分析来确定互联网上其他站点TrustRank值，然后以TR值的高低来做为网页排名的一个重要依据。跟PR值原理类似，如果其他站点获得了来自高Tr值站点的连接也将获得更高的TR值。Google TrustRank应该是以站点而不是页面为单位的。 。30排名影响GoogleTrustRank对于网站排名有种非常重要的影响：。站点内的页面在其他情况参数接近的情况下。高TR值的站点内页面将获得比其他站点页面更高的排名。高TR值站点的页面收录速度加快。因为Google对它认为重要的站点会频繁访问。获得足够的TR值的站点可以避免Sandbox。如果一个站点的信任指数太低，googl

16、e将可能会将其进行惩罚，包括进入sandbox等。如果一个站点的信任指数太低，即使其他参数非常理想，在较热门关键词上，也很难获得好的排名表现。31步骤（1/3）计算TrustRank 值首先要选择一批种子网站，然后人工查看网站，设定一个初始TrustRank 值。挑选种子网站有两种方式：选择导出链接最多的网站挑选种子网站的方法是选PR 值高的网站，因为PR 值越高，在搜索结果页面出现的概率就越大。这些网站才正是TrustRank 算法最关注的、需要调整排名的网站。那些PR 值很低的页面，在没有TrustRank 算法时排名也很靠后，计算TrustRank 意义就不大了。根据测算，挑选出两百个左

17、右网站作为种子，就可以比较精确地计算出所有网站的TrustRank值。32步骤（2/3）计算TrustRank 随链接关系减少的公式有两种方式。一是随链接次数衰减，也就是说第一层页面TrustRank 指数是一百的话，第二层页面衰减为90，第三层衰减为80。按导出链接数目分配TrustRank 值，也就是说一个页面的TrustRank 值是一百，页面上有5 个导出链接的话，每个链接将传递20%的TrustRank 值。衰减和分配两种计算方法通常综合使用，整体效果都是随着链接层次的增加，TrustRank 值逐步降低。33步骤（3/3）得出网站和页面的TrustRank 值后，可以通过两种方式影响排名。一是把传统排名算法挑选出的多个页面，根据TrustRank 值比较，重新做排名调整。设定一个最低TrustRank 值门槛，只有超过这个门槛TrustRank 值的页面，才被认为有足够的质量进入排名，低于门槛的页面将被认为是垃圾页面，从搜索结果中过滤出去。34TrustRank的弊端由于TrustRank对整体排名的影响，著名和权威