seo网页排名优化PageRank与HITS的改进算法

PageRank 算法是 1998 年由 Google 创始人SergeyBrin 和 LawrencePage 提出的基于链接分析的网页排序算法 [1 ] ,其思想是通过分析网络的链接结构来获得网络中网页的重要性排名。传统的 PageRank 算法中,对于同一网页链出时的页面等级值(PageRank )是同等对待且平均分配的,没有考虑到不同链接的重要性会有所不同,而这与 Web 链接的实际情况不符。几乎在同一时期,康奈尔大学的 Kleinberg 博士提出了 HITS算法 [2 ] ,作为同样基于链接分析的算法,该算法中引入了枢纽( Hub )页面和权威(Authority )页面的概念,两者的相互优化关系构成了 HITS 算法的基础,但是两者在迭代过程中会相互增强,对查询结果的准确性造成影响。此后,相继出现了ARC[ 3 ] 、SALSA[ 4 ] 算法等一系列以链接分析为基础的页面分级算法,并且在实际应用中取得了一定的成果。另一方面,为解决传统 PageRank 和HITS 算法中存在的不足,国内外研究者也提出了许多改进算法,如文献[5 ]提出了结合链接和内容信息的改进 PageRank 算法,其去除了 PageR-ank 算法需要的前提,考虑到了用户从一个网页直接跳转到非直接相邻但内容相关的另外一个网页的情况。文献[6 ]提出了通过在 PageRank 算法中添加链入链出权重因子、用户反馈因子、主题相关因子和时间因子,使得搜索结果更接近用户查询需求,同时兼顾了搜索内容的相关度和查准率。文献[7 ]提出利用 PageRank 算法对 Lucene原有的排序算法进行改进,设计并实现了一个针对移动信息的个性化搜索引擎。文献[8 ]提出了一种结合网页 文本分析和 扩散速率改 进的 F-HITS 算法,以解决传统 HITS 算法中易发生主题漂移、计算效率低等问题。

基于 此,本 文 通 过 分 析 传 统 PageRank 和HITS 算法中存在的不足,提出了一种基于这两种算法的改进算法 PHIA ( PageRankandHITSImprovedAlgorithm ),该算法继承了 HITS 算法获取根集和基本集的方法,并使用根集中所有网页的 PageRank 值作为 Hub 值和 Authority 值的初始迭代值,放弃了 HITS 算法中的相互迭代方式,而是通过求马尔可夫矩阵的方式来获取网页排名的静态分布

1 网页排序算法1.1 PageRank 算法PageRank 算法是根据网页超链接之间的相互关系来确定网页的重要性和排名的,基于“由许多网页或一些权威网页链接的网页必然是权威网页”的前提条件,以网页间的链接结构为基础,来划分网页的重要性等级 [9 ] 。在链接网络中,将网页 A 指向网页 B 的链接看作是 A 对 B 的投票,根据一个网页所获得的投票次数来判断网页的重要性,一个网页的 PageRank 值 PR 可由下式( 1 )

表示:PR ( i ) = ∑j ∈ Q ( i )

PR ( j )

S ( j )

(1 )

式中:i 、 j 表示网页; Q ( i )表示网页 i 指向的链接集合;S ( j )表示网页 j 指向的所有链接的数目;PR ( j )表示页面集 Q ( i )中任意一个页面 j 的 PR值;PR ( j )/ S ( j )则表示网页 i 的链入网页 j 给予网页 i 的 PR 值。

但在实际应用中, Web 连接图中常常存在一些出度或入度为 0 的节点,即存在环的情况,这时会出现两种异常:等级泄露( RankLeak )和等级下沉( RankSink )

[ 10 ] 。为避免上述现象,可以在去掉 Web 链接中所有出度为 0 的节点后,定义一个阻尼系数 d ( 0< d <1 )来表示用户随机到达一个网页的概率,只有乘以 d 部分的 PR 值才分配给其所指向的链接,而“1 — d ”的部分则平均分配给 Web 图中其他节点,由此得到式( 2 ):PR ( i ) = d ∑j ∈ Q ( i )

PR ( j )

S ( j )

+ 1- dm(2 )

式中:m 表示节点的总个数。

一个页面的 PageRank 值是由所有链向它的页面(链入页面)的重要性经过递归算法得到的,计算过程需要迭代。大量实验证明,经过反复迭代计算得到网页的 PageRank 值是收敛且有效的。 PageRank 算法作为与查询主题无关的静态算法,所有网页的 PageRank 值均可以通过后台离线计算获得,这有效地减少了在线查询时的计算量,降低了用户查询相应的时间。然而,Pag-eRank 算法的特点使其仍受制于主题漂移、偏重旧网页、忽视用户个性化等问题。

1.2 HITS 算法HITS 算法是一种基于超链接分析的网页排序算 法。该 算 法 中,网 页 被 分 为 Authority 和Hub 两种类型,所谓 Authority 页面指的是与查询主题最为相关并具有高质量、权威性的网页,Hub 页面则是指提供指向 Authority 网页链接集合的网页。同时,也为每个网页定义了两个权值,即 Authority 值和 Hub 值,用来判断该网页对特定主题的重要性。

HITS 算法的建立基于以下两点假设: ① 一个好的 Authority 页面会被很多好的 Hub 页面指向; ② 一个好的 Hub 页面会指向很多好的Au-thority 页面。该算法的具体实现过程为:Step1 将查询主题 q 提交给某搜索引擎,从返回结果页面的集合中取前 n 个结果作为根集Q , Q 需要满足: ① Q 中网页数量足够小; ② Q 中包含很多与查询相关的页面; ③ Q 中包含很多高质量的 Authority 页面。

Step2 通过向 Q 中加入被 Q 引用的网页和引用 Q 的网页,将其扩展成一个更大的集合 T 。

以 T 中的 Hub 网页为顶点集 V 1 ,以 Authority网页为顶点集 V 2 ,以 V 1 到 V 2 的超链接为边集E ,形成一个二分有向图 G = ( V 1 , V 2 , E )。对于V 1 中任一顶点 v ,用 h ( v )表示其 Hub 值;对于 V 2中任一顶点 u ,用 a (u )表示其 Authority 值。

Step3 初始化 a 、 h ,令 a 0 = h 0 =1 。

Step4 分别对 u 、 v 进行如下操作,以修改a ( u )和 h ( v )的值:① a ( u ) =∑ h ( v ); ② h ( v ) =∑ a ( u )。

Step5 对 a ( u )、 h ( v )进行规范化处理,即:① a ( u ) = a ( u )/ ∑ [ a ( ) q ]2 ;② h ( v ) = h ( v )/ ∑ [ h ( ) q ]2 。

Step6 不 断 地 重 复 Step4 和 Step5 ,直 至a ( u )、 h ( v )收敛,输出最大的 Authority 值和 Hub值。

与 PageRank 算法不同, HITS 算法与用户输入的查询请求密切相关,因而必须在接收到用户查询后进行实时计算,计算效率较低;另一方面,尽管 HITS 算法在某些查询主题下能够较为准确地提取出 Authority 网页,但若扩展网页集合里包含部分与查询主题无关的页面,且这些页面之间有较多的相互链接指向,那么使用 HITS 算法很可能会给予这些无关网页很高的排名,导致搜索结果发生“主题漂移”。此外, HITS 算法还存在易被作弊者操纵结果、结构不稳定等问题。

2 基于 PageRank 和 HITS 的改进算法 PHIA针对上述不足,本文提出了一种基于 PageR-ank 和 HITS 算法的改进算法 PHIA 。该算法继承了 HITS 算法获取根集和基本集的方法,并且使用根集中所有网页的 PageRank 值作为 Hub值和 Authority 值的初始迭代值,以避免“主题漂移”现象的发生;其次,改进算法放弃了 HITS 算法中的 Hub 值和 Authority 值相互迭代方式,而是通过求马尔可夫矩阵及其特征向量的方式来获取网页排名的静态分布,以避免其相互迭代所产生的增强值误差。算法 PHIA 的具体实现步骤为:Step1 根据用户请求,用 Google 、 Firefox等常用搜索引擎进行查询,取返回页面中的前 n个网页作为算法的根集,记为 Q 。随后对集合 Q进行扩充,方法为将根集 Q 中每一节点的入链(所有指向该节点的页面)和出链(该节点指向的所有网页)补充进来,形成基本集,记为 S Q 。

Step2 求 S Q 中页面的 PageRank 值。设 W为 S Q 中页面的集合, N =| W | , R i 为页面 i 指向的所有页面的集合,B i 为指向 i 的所有页面的集合;对每个出度为 0 或出度页面不在 S Q 中的页面s ,设 R S = { S Q 中所有页面的集合},则所有其他节点的 B i = { B i ∪ s },这样可以将结点 s 所具有的 PageRank 值均匀地传递给其他所有页面 i 。

由此,页面 i 的 PageRank 值 PR (i )可以通过以下两步计算得出: ① 以概率“1 — m ”随机取基本集S Q 中任意页面 i ; ② 以概率 m 随机取指向当前页面 i 的页面 j ,如果 j ? S Q ,则重新选择页面 j 。

PageRank 算法的具体迭代公式为:( ) PRi =1- m + m ∑j ∈ B i(PR ( j )/ | R j |(3 )

式中:参数 m 为取值范围在 0~1 范围的衰减因子,通常被置为 0.85 。

Step3 用计算得到的 PageRank 值代替 S Q集中每一个页面的 Authority 和 Hub 初始值。

从集合 S Q 构造无向图 G′ = (V h , V a , E ),得到两条链,即 Authority 链和 Hub 链:V h = ( s h | s ∈ S Q ∪ 出度( s ) >0 }(G′ 的 Hub 边)

V a = { s a | s ∈ S Q ∪ 入度( s ) >0 }(G′ 的 Authority 边)

E = {( s h , r a )} s → r in S Q }Step4 根据 2 条马尔可夫链[ 11 ] 定义其变化矩阵,也即随机矩阵,分别是 Hub 矩阵 H 和Au-thority 矩阵 A 。

H i , j =∑k : k ∈ F ( i ) ~ F ( j )

1| F ( i ) | ×1| B ( k ) |(4 )

A i , j =∑k : k ∈ B ( i ) ~ B ( j )

1| B ( i ) | ×1| F ( k ) |(5 )

Step5 求出矩阵 H 、 A 的主特征向量,即为对应的马尔可夫链的静态分布,H 、 A 中较大数值所对应的网页为所查找的重要网页。

3 实验结果及验证为验证改进 PHIA 算法的正确性和有效性,本文建立了一个实验系统,即用网络爬虫工具Heritrix 在 Google 搜索引擎上,采用 BroadScope模式对新浪微博网站的“娱乐版块”和“研究版块”

进行网页抓取。这两个板块中,各节点之间具有良好的互动关系,因此能够较好地模拟互联网的网络结构。本文随机选取“赵丽颖”和“ Web 前端”作为查询主题,由于本实验选择的新浪微博中两个板块的网页是由人工分类所形成的,并且所查询关键字的含义较为简单,故根据改进算法得到的每个网页的 Hub 值和 Authority 值是可以信赖的。

从以“赵丽颖”为主题查询得到的页面中选取前 8 个页面,分别用 A~H 表示,各页面之间的链接关系如图 1 所示。利用 PageRank 、 HITS 及改进 PHIA 算法计算各网页的权值,结果列于表1~ 表 3 中。从表 1 和表 2 中可以看出,所选择的图 1 以“赵丽颖”为搜索主题的页面链接关系Fig.1Pagelinkrelationshipwith “ ZhaoLiying ” asthesearchtopic表 1 以“赵丽颖”为搜索主题的基于 PageRank 算法的计算结果(迭代次数: 15 次)

Table1CalculationresultsbyPageRankalgorithmwith “ ZhaoLiying ” asthesearchtopic网页URL PRA https :// weibo.com / u / 5994935920 ? refer _ flag=1001030103 _ 0.0631B https :// weibo.com / u / 5261287117 ? refer _ flag=1001030103 _ 0.0925C https :// weibo.com / u / 6183821463 ? refer _ flag=1001030103 _ 0.0456D http :// s.weibo.com / list / relpage ? search=%E8%B5%B5%E4%B8%BD%E9%A2%96 0.0974E https :// weibo.com / u / 6004781311 ? refer _ flag=1001030103 _ 0.1101F https :// weibo.com / u / 2054853403 ? refer _ flag=1001030103 _ 0.1841G https :// weibo.com / u / 5022547306 ? refer _ flag=1001030103 _ 0.1565H https :// weibo.com / 210926262 ? refer _ flag=1001030101 _ 0.25088 个网页中, PageRank 值最高的页面是 H 页面,其次为 F 页面和 G 页面;最好的 Authority 页面为 F 页面和 E 页面,最好的 Hub 页面为 D 页面,其次为 E 页面和 G 页面,同时有较高的 Authori-ty权值和 Hub 权值的页面为 E 页面、 G 页面和H 页面。由表 3 所示改进 PHIA 算法的计算结果可知,具有高 Authority 值的页面为 H 页面、 F页面和 B 页面,有高 Hub 值的页面为 E 页面、 D页面和 H 页面,同时具有高 Authority 值和 Hub值的页面为 H 页面、 E 页面和 G 页面。

以“ Web 前端”为搜索主题进行查询,从返回结果网页中选取 8 个页面,分别标号为 1~8 ,其链接关系如图 2 所示, 3 种算法计算得到各网页的权值列于表 4 中。由表 4 可见,利用 PageRank算法计算得到排序第一的是页面 4 ,其次为页面 1和网页 7 ; HITS 算法下,最好的 Hub 网页为页面8 ,次为页面 5 和页面 6 ,最好的 Authority 页面为页面 4 ,其次为页面 2 ;而改进 PHIA 算法下,计算得到 Hub 值较高的页面依次为页面 5 、页面 8 和页面 1 , Authority 值较高的页面依次为页面 4 和页面 2 。

图 2 以“ Web 前端”为搜索主题的页面链接关系Fig.2Pagelinkrelationshipwith “ Webfront-end ” asthesearchtopic表 4 以“ Web 前端”为搜索主题的 3 种算法的计算结果Table4Calculationresultsbythreealgorithmswith “ Webfront-end ” asthesearchtopic网页PageRank 算法HITS 算法Hub AuthorityPHIA 算法Hub Authority1 0.1792 0.3371 0.0536 0.3668 0.12852 0.1668 0.2201 0.5179 0.1693 0.41663 0.1135 0.4058 0.1385 0.3160 0.14274 0.2113 0.3384 0.6820 0.3467 0.68455 0.0374 0.4292 0.0 0.4160 0.06 0.0479 0.4242 0.1763 0.3223 0.13717 0.1754 0.0 0.3057 0.0 0.21308 0.0684 0.4930 0.3506 0.3927 0.2325根据上述实验结果可知,基于 PageRank 和HITS 的改进算法 PHIA 能够更全面地找出所查询关键词的重要页面;更重要的是,PHIA 算法所需要的迭代次数为 10 次,少于 PageRank 算法(15 次)和 HITS 算法( 20 次)所需的迭代次数,计算量大大减少;根据对查询结果进行分析可知,页面 H 和页面 E 在内容上与搜索主题“赵丽颖”关联密切,页面 4 的内容与“ Web 前端”的关联度也相对较高。另外,当限制最大迭代次数时,若迭代次数较少,PageRank 算法得到的高 PR 值页面是随机出现的,即可能是 8 个页面中的任一页面;HITS 算法一直指向的是同一个页面,与迭代次数无关;PHIA 算法则能够找到最好的 Authority页面和 Hub 页面。可见, PHIA 算法的精度要高于 PageRank 和 HITS 算法,不足之处是当迭代次数足够多时, HITS 算法和 PHIA 算法精确度相差不大。

4 结语本文通过分析经典的基于链接分析排序算法PageRank 和 HITS 中存在的不足,提出了一种改进算法 PHIA 。该算法继承了 HITS 算法获取根集和基本集的方式,并利用根集中各网页的Pag-eRank 值作为 Hub 值和 Authority 值的初始迭代值,在一定程度上避免了“主题漂移”现象的发生;另外, PHIA 算法放弃了 HITS 算法中Hub值和 Authority 值相互迭代的方式,而是通过求马尔可夫矩阵来获取网页排名的静态分布,以解决两权值相互迭代过程中产生的增强值误差。从针对两个随机关键词的检索结果来看, PHIA 算法虽然在一定程度上削弱了主题漂移和 Hub 值和 Authority 值相互迭代导致的增强效果,并且收敛速度也有了一定的提高,但是 PHIA 算法仍然存在一些缺陷,有待进一步改进: ① PHIA 算法只是在一定程度上削弱了“主题漂移”现象的产生,并不能完全避免; ② 目前本系统只在本机中实验,未考虑到人机交互、并发等问题,故还需在实际应用中加以完善。