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

鄭 華，藍屹湘

（韶關學院 數學與統計學院， 廣東 韶關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 算法在其他領域的應用提供參考.另一方面，本文數值試驗中的參數選擇是人為設定的，在具體的應用背景中，可結合問題的實際意義設定相關的參數.