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

鄭 華，藍(lán)屹湘

（韶關(guān)學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院， 廣東 韶關(guān)512005）

PageRank［1］是Google 搜索引擎的核心算法，它由Google 公司的創(chuàng)始人Page 和Brin 所創(chuàng)立，對于按用戶提交的關(guān)鍵詞搜索得到的網(wǎng)頁，該算法基于整個互聯(lián)網(wǎng)中各個網(wǎng)頁相互之間的浩瀚鏈接關(guān)系，對網(wǎng)頁進(jìn)行等級評分(稱為PR 值)排序.PageRank 算法不但考慮了各網(wǎng)頁被指向的鏈接數(shù)量，同時還考慮了各網(wǎng)頁本身的重要性，從而使得排序所得結(jié)果更具有客觀性，廣泛受到客戶的認(rèn)可，成為互聯(lián)網(wǎng)業(yè)界各大搜索引擎的算法基礎(chǔ)，廣泛應(yīng)用于各領(lǐng)域中的不同評價推薦模型［2-3］.

由于互聯(lián)網(wǎng)的復(fù)雜性，比如孤立網(wǎng)頁的存在以及網(wǎng)站的作弊行為，在經(jīng)典的Google 搜索數(shù)學(xué)模型中，為了使得PageRank 算法結(jié)果具備合理性， 需引入阻尼系數(shù)和個性化向量對各網(wǎng)頁之間的鄰接矩陣進(jìn)行修正.在實際應(yīng)用中，阻尼系數(shù)的實際意義可以描述為用戶通過鏈接打開網(wǎng)頁的概率；另一方面，個性化向量可以有效地解決互聯(lián)網(wǎng)中孤立網(wǎng)頁對排序結(jié)果產(chǎn)生錯誤的問題.

阻尼系數(shù)和個性化向量在PageRank 算法中扮演著重要的角色，對它們的有效研究有利于PageRank算法在不同的實際問題中的推廣應(yīng)用.本文通過對阻尼系數(shù)和個性化向量的參數(shù)分析，建立相應(yīng)的排序模型，并把結(jié)果應(yīng)用到大型網(wǎng)絡(luò)系統(tǒng)，驗證模型的有效性.

在后續(xù)討論中，用AT表示矩陣A 的轉(zhuǎn)置，記＜n＞={1,2,…，n}.下面給出本文需要用到的一些基本概念.

對于矩陣A,B∈Rm×n，如果A,B 的元素滿足aij≥（＞）bij則記為A≥（＞）B；如果A≥0，稱A 為非負(fù)矩陣.

設(shè)A∈Rm×n(n≥2)，如果存在指標(biāo)集I,J∈＜n＞，滿足并且使得對都有aij=0，則稱A 是可約矩陣；否則稱A 是不可約矩陣［4］.

設(shè)A∈Rn×n且A≥0.如果A 的每行元素之和都為1，則A 稱為右隨機(jī)矩陣；如果A 的每列元素之和都為1，則稱A 為左隨機(jī)矩陣［5］.

稱n 階矩陣A 的模最大特征值為A 的主特征值，其對應(yīng)的特征向量稱為主特征向量［6］.

1 基于參數(shù)分析的排序推薦模型

定義［1］設(shè)0＜d＜1, v≥0 是n 維非負(fù)向量，e 是元素全為1 的n 維向量，B∈Rn×n表示描述互聯(lián)網(wǎng)中各網(wǎng)頁鏈接關(guān)系的鄰接矩陣的歸一化結(jié)果(即B 是一個右隨機(jī)矩陣)，稱A=［dB+(1-d)evT］T為Google 矩陣.

引理［3］如果A 是n 階不可約的非負(fù)矩陣，那么A 的主特征值為單根，主特征向量為正向量.

使用PageRank 算法計算各網(wǎng)頁PR 值的基本步驟為：

第1 步：從互聯(lián)網(wǎng)獲取表示網(wǎng)頁之間鏈接關(guān)系的鄰接矩陣；

第2 步：對鄰接矩陣進(jìn)行修正得到Google 矩陣；

第3 步：用冪法［7］計算Google 矩陣的主特征向量（即按模最大的特征值對應(yīng)的特征向量）；

第4 步：把主特征向量進(jìn)行歸一化后得到各網(wǎng)頁的PR 值.

在Google 矩陣的定義中，d 一般稱為阻尼系數(shù)，其意義是認(rèn)為用戶在瀏覽網(wǎng)頁的時候，有d 的概率是通過網(wǎng)頁鏈接的方式打開新的網(wǎng)頁，而通過屬于網(wǎng)址的形式打開新網(wǎng)頁的概率為1-d，在經(jīng)典的Google搜索模型中，Google 創(chuàng)始人Page 把阻尼系數(shù)的取值設(shè)定為d=0.85. 另一個參數(shù)向量v 一般稱為個性化向量，其存在的意義包括兩方面，一是保證Google 矩陣具有非負(fù)不可約性質(zhì)，從而根據(jù)引理的結(jié)論確保PageRank 算法的第3 步由冪法計算得到的主特征向量為正向量；另一方面，結(jié)合阻尼系數(shù)，個性化向量也能解決互聯(lián)網(wǎng)中不具備相應(yīng)鏈接關(guān)系孤立網(wǎng)頁的存在問題，使得PageRank 算法的計算結(jié)果具有實際意義.

隨著互聯(lián)網(wǎng)的不斷發(fā)展，在PageRank 的實際應(yīng)用中，用戶訪問網(wǎng)頁的方式趨于多樣化，結(jié)合不同應(yīng)用背景的特征，對個性化向量的設(shè)定提出了更高的要求.接下來，從阻尼系數(shù)和個性化向量這兩個參數(shù)入手，通過數(shù)值分析方法分析這些參數(shù)對PageRank 排序結(jié)果的影響.

1.1 阻尼系數(shù)

由于互聯(lián)網(wǎng)中大量孤立網(wǎng)頁的存在，導(dǎo)致網(wǎng)頁的鄰接矩陣有某些列向量全為0，這將導(dǎo)致冪法計算結(jié)果的不可靠性.阻尼系數(shù)的引入不但考慮了用戶除鏈接以外的打開新網(wǎng)頁方式，在數(shù)學(xué)意義上還可均勻填充由孤立網(wǎng)頁產(chǎn)生的全零列，進(jìn)而保證冪法的收斂性.由Google 矩陣的定義可見，阻尼系數(shù)的大小直接影響了鄰接矩陣全零列的填充權(quán)重，建立數(shù)學(xué)模型如下：

模型1(阻尼系數(shù)的擾動分析)

初始化：給定0-1 鄰接矩陣B，初始向量u，個性化向量v.

輸出：記錄u 的前若干個分量的原始序號變化.

注1：在模型1 中，初始化中的個性化向量v 可取為Page 測試PageRank 算法所使用的這里N 表示鄰接矩陣的階數(shù)；在結(jié)果輸出中，參考目前主流搜索引擎Google 和百度的默認(rèn)設(shè)置，可取前10 個分量.

1.2 個性化向量

從Google 矩陣的定義可知，個性化向量決定了以概率填充鄰接矩陣全零列的修正項的各分量比重，會直接影響PageRank 計算結(jié)果，因此個性化向量往往是各搜索引擎公司的商業(yè)秘密.為了分析其分量變化對計算所得的主特征向量分量權(quán)重的影響，采用集中個別分量權(quán)重的方式進(jìn)行分析，同時，過程中注意調(diào)整個性化向量的其他分量大小，保證修正策略的合理性，具體模型如下：

模型2(個性化向量的擾動分析)

初始化：給定0-1 鄰接矩陣B，初始向量u，阻尼系數(shù)d，閾值σ.

輸出：記錄u 的第i*個分量的序號變化.

注2： 在模型2 中， 初始化中的阻尼系數(shù)d 可取為Page 測試PageRank 算法所使用的d=0.85：vj=的設(shè)定是為了保證所得的Google 矩陣仍然是右隨機(jī)矩陣.

2 數(shù)值試驗

本節(jié)通過數(shù)值試驗展示模型1 和模型2 的分析效果.

數(shù)值試驗的運行環(huán)境是Intel(R) Core(TM) 2.50 GHz，計算機(jī)內(nèi)存為4 G，編程語言為MATLAB.試驗采用的0-1 鄰接矩陣來源于University of Florida Sparse Matrix Collection（https：//sparse.tamu.edu/），鄰接矩陣的詳細(xì)信息為（名稱：web-Google；背景：Google 有向圖；階數(shù)N：916 428；非零元個數(shù)：5 105 039）.

取初始向量為e，冪法收斂的誤差上限設(shè)定為10-8，先取d=0.85,可計算得到排名前10 的網(wǎng)頁序號依次為：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 的網(wǎng)頁序號，如表1 所示.

表1 阻尼系數(shù)擾動導(dǎo)致的網(wǎng)頁序號（1～10）排序變化

由表1 可見，當(dāng)阻尼系數(shù)在［0.83，0.89］之間變化時，網(wǎng)頁排名較為穩(wěn)定，Page 在提出PageRank 算法的時候所使用的0.85 屬于這個區(qū)間，這是由web-Google 的數(shù)據(jù)來源決定的，由此也可以看出模型1 的合理性.

在模型2 中，考慮表2 中d=0.85 的情形，考慮以下兩種干預(yù)排名的方式：

方式1：取排名第10 的網(wǎng)頁(序號為78 920)，誤差上限不變，閾值設(shè)定為即設(shè)置為默認(rèn)元素的兩倍大小.

方式2：取排名第9 和第10 的網(wǎng)頁(序號為70 210 和78 920)，誤差上限不變，閾值都設(shè)定為

按冪法計算所得的排名前10 的網(wǎng)頁序號如表2 所示.

表2 個性化向量擾動導(dǎo)致的網(wǎng)頁序號排序變化

由表2 可見，以兩種方式對個性化向量的分量權(quán)重增加以后，直接把兩個網(wǎng)頁的排名提升到了第一.這表明，模型2 對個性化向量的擾動干預(yù)方式是有效的.

3 結(jié)論

模型1 和模型2 分別從阻尼系數(shù)和個性化向量兩個角度對PageRank 算法的運行進(jìn)行了擾動分析,對大規(guī)模稀疏Google 有向圖矩陣的數(shù)值試驗表明了本文兩個模型的有效性, 本文的分析方法可以對PageRank 算法在其他領(lǐng)域的應(yīng)用提供參考.另一方面，本文數(shù)值試驗中的參數(shù)選擇是人為設(shè)定的，在具體的應(yīng)用背景中，可結(jié)合問題的實際意義設(shè)定相關(guān)的參數(shù).