PageRank問題改進下的多分裂迭代法分析

程軍

【摘要】近年來，互聯網科技發展迅猛，網絡搜索引擎的PageRank問題逐漸成為焦點.因此，我們以此為出發點進一步探究獲得了多分裂迭代法，并對PageRank問題改進下的多分裂迭代法做出了研究和分析.本文從內外迭代法出發，分析了多分裂迭代算法的過程，并在此基礎上對多分裂迭代法提出了改進，重點對IMSI算法以及MMSI算法進行了分析和研究，并對其收斂性進行了介紹，最后用數值試驗驗證了IMSI算法及MMSI算法在求解PageRank問題中的優勢.

【關鍵詞】PageRank問題;改進;多分裂迭代法

【基金項目】云南省教育廳科學研究基金項目（2019J0610，2018JS438），曲靖市教育體育局-曲靖師范學院教育科學規劃科學研究基金項目（QJQSKT2019YB11），曲靖師范學院科學研究基金項目（2020ZX010）.

隨著互聯網技術的飛速發展，人類加速進入信息時代，如何利用更好的搜索引擎從而更加高效地獲取信息成了一個重要問題.而算法作為搜索引擎的核心，要提高其速度，必須最大程度縮小從搜索目標到頁面反饋這一過程的滯后時間，從而提高信息檢索的質量.1998年鏈式分析技術的出現以及PageRank算法的提出使網絡搜索引擎越來越能夠滿足用戶們對網絡信息服務的高質量要求，網絡鏈接分析也因此逐漸占據權威地位.基于網頁重要性進行排序從而獲得查詢結果的PageRank算法大大提升了引擎的搜索效果，其核心技術是計算代表網絡超鏈接結構的Google矩陣的特征向量.

一、多分裂迭代算法（MSI算法）

首先矩陣 I-αP可以寫為：

I-αP=（I-β1P）-（α-β1P）=（I-β2P）-（α-β2P）.

其中0< β1<α，0<β2<α，給出初始向量{x（0）}，k=0，1，2，…，進行迭代：

（I-β1P）x（k+1）=（α-β1）Px（k）+（1-α）v，

（I-β2p）x（k+1）=（α-β2）Px（k）+（1-α）v，（1）

直到向量序列{x（k）}收斂到給定的精度.由此可得多分裂迭代算法：

輸入： 給定矩陣P，v，參數α，β1，β2，η和γ

輸出：x

1：迭代開始

2：x=v;

3：z=Px;

4：當||αz+ （1-α）v-x||1≥γ時;

5：f1= （-β1）z+（1-α）v;

6：重復

7：x=f1+ β1z;

8：z=Px;

9： 直到||f1+β1z-x||1<η，

10：f2= （-β2）z+（1-α）v;

11：重復

12：x=f2+β2z;

13：z=Px;

14：直到||f2+β2z-x||1<η，

15：結束

16：x=αz+（1-α）v;

二、改進的多分裂迭代算法

從2015年的兩步分裂迭代法，到2017年的MPIO迭代法，再到2018年的GMRES-Power迭代法的提出，我們可以知道近年來關于加速求解PageRank問題的進程從未停止.而通過改進多分裂迭代算法可以滿足加速求解PageRank問題這一需求，下面主要介紹兩種，即利用增加參數的方法控制阻尼因子的取值范圍，減小譜半徑，進而加速收斂的IMSI算法，及將多重分裂迭代法的第一重分裂進行多步迭代再結合第二重分裂來加速的MMSI算法.

（一）IMSI算法

在求解PageRank問題中，問題的難度會隨著我們選取的阻尼因子的減小而變得簡單，于是我們嘗試在多分裂迭代算法的基礎上用再引入一個參數的方法控制阻尼因子的范圍，讓譜的半徑更小從而加速收斂.以下簡稱該方法為IMSI算法.

給出初始向量{x（0）}，k=0，1，2，…，進行迭代：

（I-β1P）x（k，1）=（α-β1）Px（k）+（1-α）v，

（I-β2P）x（k，2）=（α-β2）Px（k，1）+（1-α）v，

（I-β3P）x（k+1）=（α-β3）Px（k，2）+（1-α）v，（2）

（0< β1<α，0<β2<α，0<β3<α）當向量序列{x（k）}收斂停止迭代，得到算法：

輸入：P，β1，β2，β3，η，γ，v

輸出：x

1：迭代開始

2：x=v;

3：z=Px;

4：當||αz+ （1-α）v-x||1≥γ時;

5：f1= （-β1）z+（1-α）v;

6：重復

7：x=f1+β1z;

8：z=Px;

9： 直到||f1+β1z-x||1<η，

10：f2= （-β2）z+（1-α）v;

11：重復

12：x=f2+β2z;

13：z=Px;

14：直到||f2+β2z-x||1<η;

15： f3= （-β3）z+（1-α）v;

16：重復

17：x=f3+β3z;

18：z=Px;

19：直到||f3+β3z-x||1<η;

20：結束

21：x=αz+（1-α）v;

1.IMSI算法的收斂性

對線性系統系數矩陣I-αP進行分裂：