改进PageRank算法的网页权重分析

黄 艳，李朝荣

（宜宾学院人工智能与大数据学部，四川宜宾 644000）

使用网页搜索引擎时，系统需要根据网页的重要性将搜索的网页推荐给用户，以提高系统人性化和智能化水平. 网页中的链接（包括数量和质量）和主题内容是网页排序的两个关键依据[1]. 网页中的链接较多，其链接指向的其他网页质量较高，则该网页通常是较重要的网页；网页主题内容如果是热点，或者与用户的关键词更相关，也会让该网页排序更靠前[2].常见的网页排序有以下几种：

（1）基于关键词统计的排序[3]

利用关键词在网页中出现的频率和重要性排序是搜索引擎最早期排序的主要思想，其技术发展也最为成熟，是第一代搜索引擎使用的主要技术，至今仍是主流搜索引擎必备的排序技术. 其实现的基本依据是，关键词在网页中词频越高、越重要，则被认为与用户检索的词的匹配程度越好.

（2）基于链接分析的排序[4]

根据链接分析进行网页排序的主要思想是：如果某网页被别的网页引用的次数越多，并且这些引用的网页越权威，则该网页的价值就越大. 被别的网页引用次数越多，说明该网页受到的关注程度比较高；被越权威的网页引用，说明该网页质量越高.基于链接分析排序算法可以归结为两大类：基于随机漫游模型的算法，最典型的就是PageRank[5]；基于概率模型的算法，常见的模型有SALSA和HITS[6].

（3）综合主题内容的排序

综合主题内容的排序也称为智能化排序，属于第三代搜索引擎涉及的范畴. 该类方法除了考虑上述两种传统的排序技术外，还要重点考虑网页内容和用户搜索内容的相关性来排序网页. 由于语言文本的复杂性和模糊性，仅仅通过链接分析及网页的表面特征来判断检索词与网页的相关性是片面的，因而需要利用机器学习、人工智能等相关技术分析网页内容. 目前流行的技术包括基于向量空间模型的SVM 模型[7]，以及基于深度网络的BERT[8]、Transformer[9]等文本分析模型.

1 PageRank 算法分析及其改进

1.1 PageRank算法

PageRank 是Google 用于标识网页等级（也称为重要性）的一种方法，是用来衡量一个站点好坏的一种标准. 在揉合了诸如网页标题和关键字等标识后，通过PageRank 调整结果，使那些更具“等级/重要性”的网页在搜索结果中令站点排名获得提升，从而提高搜索结果的相关性和质量. PageRank 利用网页之间的链接关系，计算出代表网页重要程度的值（PageRank 值，简称PR值）来排序网页，PR值越高，说明该网页越受欢迎（越重要）.

PageRank 算法基于两个假设：①如果某网页被很多网页引用，则该网页是一个重要网页，称为数量假设；②如果有高质量的网页（权威网页）指向某网页，则该网页也是一个重要网页，称为质量假设.PageRank算法的核心公式如下：

其中：PR(pi)是网页pi的PageRank 值，M(pi)是链入pi网页的集合，L(pj)是网页pj链出网页的数量，N是集合中所有网页的数量，d为阻尼因子，通常取0.85[9]. 集合中所有网页的PR值可以用一个向量A来表示：

根据PageRank 公式（1），公式（2）可以写成如下的矩阵形式迭代公式：

其中：At是在t步迭代时所有网页的PR值.l(pi，pj)表示从网页j指向网页i的链接数与网页j中含有的外部链接总数的比值；如果pi和pj之间没有链接，则l(pi，pj)=0.

PageRank有如下的优缺点：

优点：PageRank 是一个与查询无关的静态算法，所有网页的PR值通过离线计算获得；能有效减少在线查询时的计算量，极大降低了查询响应时间.

缺点：PageRank 只根据网页的链接情况来分析重要性，忽略了主题相关性和环境等因素，导致排序的结果不是很合理. 例如一个新网页，即使该网页受到较多关注也不会有很多上游链接，其排序会较低，除非它是某个子站点.

1.2 改进的PageRank算法：EPageRank

通常衡量一个网页的重要性还应包括：

（1）网页的点击量：网页的点击量高，说明网页越受关注，也越重要.

（2）时间因素：时间越久（越老）的网页，其重要程度要降低.

为了克服PageRank 的缺陷，本文提出了改进的PageRank算法，称为EPageRank，其PR值计算如下：

其中：hi表示点击量因子，值越大点击量越高，对PR值贡献越多；ti表示时间因子，数值越大对PR值贡献越小.

2 实验与分析

阻尼系数d的含义是，在任意时刻，用户到达某网页后并继续浏览该网页的概率，同义，可以理解1-d是用户到达某网页后离开（跳转到其他网页）的概率. 为了说明d在算法中的作用，本文设计了4 个网页的集合[A，B，C，D]，网页之间的链接关系如图1所示. 图中的边是有向箭头，箭头指向表示该网页包含另外一个网页的链接（从该网页能够跳转到另外一个网页）.例如A→D表示A包含指向网页D的链接，A↔C表示A包含C的链接，C也包含A的链接.

图1 网页及其之间的链接关系

将阻尼系数d设置变化从0.2 到0.95，分别计算四个网页的PR值，结果见表1. 可以看出阻尼系数会影响PR值，但是对于排序并没有多大影响，表1中四个网页的排序均为2、3、1、4. 这说明PR值及其排序主要是网页及其包含的链接所决定的，阻尼系数、网页主题等因素对网页的排序影响非常有限.

表1 不同阻尼系数下的网页PR值及其排序

观察EPageRank中阻尼系数d以及点击量、时间因子等对PR值及其排序的影响，将点击量和时间因子均设置为1～8 个值（根据情况可以设置为其它的值），设置情况见表2. 点击量因子h由点击量确定，例如0～10次点击量，该网页的点击量因子h设置为1；11～50 次点击量，h设置为2. 时间因子t则根据网页存在的天数来确定，例如网页存在0～1 天，该网页的时间因子t设置为1；2～3天，t设置为2.

表2 点击量和时间因子设置

表3和表4列出了EPageRank的评估结果.

表3 EPageRank排序结果（A(8，1)，B(3，6)，C(7，2)，D(5，5)）

表4 EPageRank排序结果（A(1，5)，B(1，7)，C(8，3)，D(8，6)）

表中的X(h，t)表示网页X的点击量因子为h、时间因子为t，如A(8，1)表示网页A的点击量因子为8，该网页的点击量比较高，时间因子为1，表示该网页比较新. 由于EPageRank 采用了log10，PR值可能为负数，具体见表4. 从两个表的结果可以看出，由于时间和点击量因子加入，阻尼系数对PR值的影响力加大. 这说明时间和点击量会影响该网页，对用户在该网页继续浏览和跳转到其他网页的影响力增大，更加符合实际情况. 在同样的网页及其链接关系下，网页的点击量和网页存在时间，会明显改变网页排序结果. 同样的阻尼系数0.5，当四个网页的点击量和时间因子分别是A(8，1)、B(3，6)、C(7，2)、D(5，5)，其排序情况是1、2、3、4；当四个网页的点击量和时间因子分别是A(1，5)、B(1，7)、C(8，3)、D(8，6)时，其排序情况是3、4、1、2. 结合表1、表3 和表4，可以看出网页A在PageRank 下的排序为2，当考虑时间和点击量因子为A(8，1)时（说明该网页点击量高，也比较新），其排名提升到第一位；当为A(1，5)时（说明该网页点击量低，存在时间也比较久）其排名降低到第三位.

3 总结

本文提出了PageRank 的改进版，在进行网页排序时，除了考虑网页链接关系外，还加入了点击量和时间因子，以此弥补PageRank 的不足，更加切合实际应用. 本文对点击量和时间因子的设置可能不够完善，还可以根据实际情况进行设置；EPageRank 的公式中采用了对数形式，该形式不唯一，可以考虑使用其他不同的形式.