羅 慧，馬昌鳳2

（福建師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建，福州 350117）

0 引言

隨著互聯(lián)網(wǎng)及其技術(shù)的蓬勃發(fā)展,網(wǎng)絡(luò)搜索引擎已經(jīng)成為檢索信息最受歡迎的工具。作為Google的關(guān)鍵技術(shù)PageRank 算法在過(guò)去十幾年中一直受到科學(xué)界學(xué)者的關(guān)注。簡(jiǎn)而言之PageRank 問(wèn)題可看作Google 矩陣首特征值1 所對(duì)應(yīng)特征向量的求解。

Google 矩陣的定義如下：

為解決PageRank 問(wèn)題，冪法是易于計(jì)算的且最經(jīng)典的算法，但當(dāng)阻尼因子α接近1 時(shí)，冪法收斂速度非常慢。為了改進(jìn)冪法，Gleich 等[1]利用Richardson 迭代法提出了內(nèi)外迭代法。Gu 等人將冪法和內(nèi)外迭代法相結(jié)合，在文獻(xiàn)[2]里提出了兩步分裂迭代PIO 算法。隨后，Gu 等人將多步冪法與內(nèi)外迭代相結(jié)合，在文獻(xiàn)[3]中開(kāi)發(fā)了PIO 迭代的一種變體,也就是MPIO 方法，最近Pu 等人在文獻(xiàn)[4]中介紹了一種基于多步冪法和多步分裂的IO 迭代的變體，用MPMIO 來(lái)表示。在以上文獻(xiàn)的基礎(chǔ)上，本研究提出了IO（PIO）迭代的一種變式，將多步冪法和多步分裂的IO 迭代的結(jié)合擴(kuò)展到更為一般的情形，以加速PageRank 的計(jì)算。

1 內(nèi)外迭代法

2 修正多步冪-多分裂內(nèi)外迭代法（GPTI）

3 GPTI 算法的全局收斂性分析

本節(jié)我們主要分析所提出的算法在沒(méi)有任何阻尼因子和停止誤差下的全局收斂性情況。

4 數(shù)值實(shí)驗(yàn)

表1 測(cè)試矩陣的性質(zhì)Table 1 Properties of the test matrix

數(shù)值算例2

在本例中，將算例1 中矩陣換為維數(shù)更大，稠密度更小的測(cè)試矩陣Wiki-Talk，運(yùn)算結(jié)果如表3 與算例1 類似。圖2 描述了Wiki-Talk 矩陣在阻尼因子α取不同值時(shí)4 種算法的收斂軌跡，也說(shuō)明GPTI 算法比其他三種算法收斂速度更快。

圖1 Amazon0312 矩陣的測(cè)試結(jié)果Fig.1 Amazon0312 矩陣的測(cè)試結(jié)果

圖2 Wiki-Talk 矩陣四種算法的收斂效果Fig.2 Wiki-Talk test results for the matrix

表2 Amazon0312 矩陣的測(cè)試結(jié)果Table 2 Test results for the Amazon 0312 matrix

表3 Wiki-Talk 矩陣的測(cè)試結(jié)果Table 3 Test results for the Wiki-Talk matrix