基于阻尼系数和个性化向量修正的排序模型

郑 华，蓝屹湘

（韶关学院 数学与统计学院， 广东 韶关512005）

PageRank［1］是Google 搜索引擎的核心算法，它由Google 公司的创始人Page 和Brin 所创立，对于按用户提交的关键词搜索得到的网页，该算法基于整个互联网中各个网页相互之间的浩瀚链接关系，对网页进行等级评分(称为PR 值)排序.PageRank 算法不但考虑了各网页被指向的链接数量，同时还考虑了各网页本身的重要性，从而使得排序所得结果更具有客观性，广泛受到客户的认可，成为互联网业界各大搜索引擎的算法基础，广泛应用于各领域中的不同评价推荐模型［2-3］.

由于互联网的复杂性，比如孤立网页的存在以及网站的作弊行为，在经典的Google 搜索数学模型中，为了使得PageRank 算法结果具备合理性， 需引入阻尼系数和个性化向量对各网页之间的邻接矩阵进行修正.在实际应用中，阻尼系数的实际意义可以描述为用户通过链接打开网页的概率；另一方面，个性化向量可以有效地解决互联网中孤立网页对排序结果产生错误的问题.

阻尼系数和个性化向量在PageRank 算法中扮演着重要的角色，对它们的有效研究有利于PageRank算法在不同的实际问题中的推广应用.本文通过对阻尼系数和个性化向量的参数分析，建立相应的排序模型，并把结果应用到大型网络系统，验证模型的有效性.

在后续讨论中，用AT表示矩阵A 的转置，记＜n＞={1,2,…，n}.下面给出本文需要用到的一些基本概念.

对于矩阵A,B∈Rm×n，如果A,B 的元素满足aij≥（＞）bij则记为A≥（＞）B；如果A≥0，称A 为非负矩阵.

设A∈Rm×n(n≥2)，如果存在指标集I,J∈＜n＞，满足并且使得对都有aij=0，则称A 是可约矩阵；否则称A 是不可约矩阵［4］.

设A∈Rn×n且A≥0.如果A 的每行元素之和都为1，则A 称为右随机矩阵；如果A 的每列元素之和都为1，则称A 为左随机矩阵［5］.

称n 阶矩阵A 的模最大特征值为A 的主特征值，其对应的特征向量称为主特征向量［6］.

1 基于参数分析的排序推荐模型

定义［1］设0＜d＜1, v≥0 是n 维非负向量，e 是元素全为1 的n 维向量，B∈Rn×n表示描述互联网中各网页链接关系的邻接矩阵的归一化结果(即B 是一个右随机矩阵)，称A=［dB+(1-d)evT］T为Google 矩阵.

引理［3］如果A 是n 阶不可约的非负矩阵，那么A 的主特征值为单根，主特征向量为正向量.

使用PageRank 算法计算各网页PR 值的基本步骤为：

第1 步：从互联网获取表示网页之间链接关系的邻接矩阵；

第2 步：对邻接矩阵进行修正得到Google 矩阵；

第3 步：用幂法［7］计算Google 矩阵的主特征向量（即按模最大的特征值对应的特征向量）；

第4 步：把主特征向量进行归一化后得到各网页的PR 值.

在Google 矩阵的定义中，d 一般称为阻尼系数，其意义是认为用户在浏览网页的时候，有d 的概率是通过网页链接的方式打开新的网页，而通过属于网址的形式打开新网页的概率为1-d，在经典的Google搜索模型中，Google 创始人Page 把阻尼系数的取值设定为d=0.85. 另一个参数向量v 一般称为个性化向量，其存在的意义包括两方面，一是保证Google 矩阵具有非负不可约性质，从而根据引理的结论确保PageRank 算法的第3 步由幂法计算得到的主特征向量为正向量；另一方面，结合阻尼系数，个性化向量也能解决互联网中不具备相应链接关系孤立网页的存在问题，使得PageRank 算法的计算结果具有实际意义.

随着互联网的不断发展，在PageRank 的实际应用中，用户访问网页的方式趋于多样化，结合不同应用背景的特征，对个性化向量的设定提出了更高的要求.接下来，从阻尼系数和个性化向量这两个参数入手，通过数值分析方法分析这些参数对PageRank 排序结果的影响.

1.1 阻尼系数

由于互联网中大量孤立网页的存在，导致网页的邻接矩阵有某些列向量全为0，这将导致幂法计算结果的不可靠性.阻尼系数的引入不但考虑了用户除链接以外的打开新网页方式，在数学意义上还可均匀填充由孤立网页产生的全零列，进而保证幂法的收敛性.由Google 矩阵的定义可见，阻尼系数的大小直接影响了邻接矩阵全零列的填充权重，建立数学模型如下：

模型1(阻尼系数的扰动分析)

初始化：给定0-1 邻接矩阵B，初始向量u，个性化向量v.

输出：记录u 的前若干个分量的原始序号变化.

注1：在模型1 中，初始化中的个性化向量v 可取为Page 测试PageRank 算法所使用的这里N 表示邻接矩阵的阶数；在结果输出中，参考目前主流搜索引擎Google 和百度的默认设置，可取前10 个分量.

1.2 个性化向量

从Google 矩阵的定义可知，个性化向量决定了以概率填充邻接矩阵全零列的修正项的各分量比重，会直接影响PageRank 计算结果，因此个性化向量往往是各搜索引擎公司的商业秘密.为了分析其分量变化对计算所得的主特征向量分量权重的影响，采用集中个别分量权重的方式进行分析，同时，过程中注意调整个性化向量的其他分量大小，保证修正策略的合理性，具体模型如下：

模型2(个性化向量的扰动分析)

初始化：给定0-1 邻接矩阵B，初始向量u，阻尼系数d，阈值σ.

输出：记录u 的第i*个分量的序号变化.

注2： 在模型2 中， 初始化中的阻尼系数d 可取为Page 测试PageRank 算法所使用的d=0.85：vj=的设定是为了保证所得的Google 矩阵仍然是右随机矩阵.

2 数值试验

本节通过数值试验展示模型1 和模型2 的分析效果.

数值试验的运行环境是Intel(R) Core(TM) 2.50 GHz，计算机内存为4 G，编程语言为MATLAB.试验采用的0-1 邻接矩阵来源于University of Florida Sparse Matrix Collection（https：//sparse.tamu.edu/），邻接矩阵的详细信息为（名称：web-Google；背景：Google 有向图；阶数N：916 428；非零元个数：5 105 039）.

取初始向量为e，幂法收敛的误差上限设定为10-8，先取d=0.85,可计算得到排名前10 的网页序号依次为：177，13 874，15 829，23 729，32 689，45 264，53 991，60 682，70 210，78 920.

在模型1 中，取d=0.75∶0.2∶0.95,（这里“∶”是MATLAB 运算符［8］），误差上限和v 不变，按幂法计算所得的排名前10 的网页序号，如表1 所示.

表1 阻尼系数扰动导致的网页序号（1～10）排序变化

由表1 可见，当阻尼系数在［0.83，0.89］之间变化时，网页排名较为稳定，Page 在提出PageRank 算法的时候所使用的0.85 属于这个区间，这是由web-Google 的数据来源决定的，由此也可以看出模型1 的合理性.

在模型2 中，考虑表2 中d=0.85 的情形，考虑以下两种干预排名的方式：

方式1：取排名第10 的网页(序号为78 920)，误差上限不变，阈值设定为即设置为默认元素的两倍大小.

方式2：取排名第9 和第10 的网页(序号为70 210 和78 920)，误差上限不变，阈值都设定为

按幂法计算所得的排名前10 的网页序号如表2 所示.

表2 个性化向量扰动导致的网页序号排序变化

由表2 可见，以两种方式对个性化向量的分量权重增加以后，直接把两个网页的排名提升到了第一.这表明，模型2 对个性化向量的扰动干预方式是有效的.

3 结论

模型1 和模型2 分别从阻尼系数和个性化向量两个角度对PageRank 算法的运行进行了扰动分析,对大规模稀疏Google 有向图矩阵的数值试验表明了本文两个模型的有效性, 本文的分析方法可以对PageRank 算法在其他领域的应用提供参考.另一方面，本文数值试验中的参数选择是人为设定的，在具体的应用背景中，可结合问题的实际意义设定相关的参数.