畢業(yè)論文 對(duì)GOOGLE搜索引擎中網(wǎng)頁(yè)排序算法的研究

1、武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文武漢紡織大學(xué)畢畢 業(yè)業(yè) 設(shè)設(shè) 計(jì)計(jì) 論論 文文 題題 目目： 對(duì)對(duì) Google 搜索引擎中網(wǎng)頁(yè)排序算法的研究搜索引擎中網(wǎng)頁(yè)排序算法的研究 武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文摘 要搜索引擎技術(shù)的發(fā)展是隨著電子技術(shù)不斷進(jìn)步的信息數(shù)字化和數(shù)據(jù)網(wǎng)絡(luò)化的必然產(chǎn)物，網(wǎng)頁(yè)排序算法一直是搜索引擎的核心技術(shù)之一。Google 搜索引擎依靠其 PageRank 機(jī)制及收斂算法一直處于該領(lǐng)域的領(lǐng)先地位。本文深入研究PageRank 排名算法，從數(shù)學(xué)的角度來(lái)看，發(fā)現(xiàn)它能夠通過(guò)計(jì)算一個(gè)基于網(wǎng)絡(luò)連接圖的轉(zhuǎn)移概率矩陣的主特征向量 (PageRank 向量)實(shí)現(xiàn)。同時(shí)針對(duì)網(wǎng)絡(luò)的復(fù)v

2、雜情形,對(duì)轉(zhuǎn)移概率矩陣作出了修正并分析了修正矩陣的特性。(1)PPE給出了計(jì)算主特征向量的數(shù)值解法-冪法。利用修正矩陣中鏈接矩陣的稀疏PP性，優(yōu)化了冪法在迭代中的計(jì)算量并減少了存儲(chǔ)空間.在冪法理論基礎(chǔ)上，給出了一種較新的加速收斂的外推法-The Vector -algorithm，最后結(jié)合一個(gè)現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)的數(shù)據(jù)測(cè)試，驗(yàn)證了該外推法的良好的實(shí)際運(yùn)用效果。關(guān)鍵詞關(guān)鍵詞：搜索引擎；PageRank；轉(zhuǎn)移概率矩陣；主特征向量；加速收斂；外推法；冪法；The Vector -algorithm武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文ABSTRACTWith the development of ele

3、ctronic technology, the search engine technology is becoming more and more important. Google search engine keeps on the top by its PageRank and convergence algorithm. We will see that, from the mathematical point of view, it could be solved by computing the principal eigenvector (the PageRank vector

4、) of a Transition Probability Matrix of the Web. According to the Webs complexity, we will give the modified matrix , and also analyze its (1)PPEcharacteristics. We will study the mathematical properties of the power method that computing the PageRank vector. We use the sparse of the Web matrix in t

5、he Piterative matrix , optimize the computation of each iteration and reduce its storage Pspace. The Vector -algorithm, an extrapolation algorithm for vector sequences, is proposed based on the power method. It will achieve the higher rate convergence in the computing performance of power method. Fi

6、nally, some simulation work of the theoretical proof will be verified by the satisfied practical results.Keywords：Search Engine; PageRank; Transition Probability Matrix; principal eigenvector; convergence and acceleration; extrapolation; power method; The Vector -algorithm武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文目 錄1. 緒論

7、11.1 引言11.2 PAGERANK簡(jiǎn)介21.3 本文的主要內(nèi)容和結(jié)構(gòu)安排32. 基本的 PAGERANK 模型42.1 PAGERANK的基本概念42.2 PAGERANK的基本模型52.3 存在的問(wèn)題82.3.1 懸點(diǎn)(Dangling Nodes)82.3.2 主特征向量空間()TL P不是一維的82.4 對(duì)上述問(wèn)題的修正92.4.1 對(duì)出現(xiàn)懸點(diǎn)的修正92.4.2 對(duì)dim( ()2TL P的修正103. 對(duì) PAGERANK 問(wèn)題的求解方法103.1 冪法113.2 在 PAGERANK上的冪法123.2.1 初始優(yōu)化 PageRank 矩陣123.2.2 冪法的偽代碼13武漢紡織

8、大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文4. 冪法加速144.1 外推法144.1.1 The vector -algorithm144.1.2 The vector -algorithm 偽代碼155. 應(yīng)用165.1 對(duì)簡(jiǎn)化的網(wǎng)絡(luò)進(jìn)行等級(jí)分析165.2 對(duì)一個(gè)現(xiàn)實(shí)的復(fù)雜網(wǎng)絡(luò)進(jìn)行分析186. 結(jié)語(yǔ)與展望20參考文獻(xiàn)22武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文1 緒論1.1 引言當(dāng)前因特網(wǎng)上有大量站點(diǎn)正在不斷地從廣大用戶當(dāng)中搜索數(shù)據(jù)，并利用機(jī)器學(xué)習(xí)和統(tǒng)計(jì)方法從中獲得需要的信息。Google 搜索引擎作為其中的佼佼者，它不僅可以利用網(wǎng)絡(luò)鏈接對(duì)網(wǎng)頁(yè)進(jìn)行排名，而且當(dāng)其廣告被不同的用戶選定時(shí)，它會(huì)持續(xù)搜集信息，這

9、使得 Google 能夠更加有效地進(jìn)行廣告定位。它目前被公認(rèn)為是全球規(guī)模最 大的搜索引擎，它提供了簡(jiǎn) 便人性化的各種免費(fèi)服務(wù)，用戶可以在很短的時(shí)間內(nèi) 得到相關(guān)的搜索結(jié)果。 一個(gè)優(yōu)秀的搜索引擎應(yīng)該及時(shí)向用戶提供所需要的最重要最有價(jià)值的網(wǎng)頁(yè)信息并將其排在前面，然而這種及時(shí)，高效，高質(zhì)量的顯示結(jié)果必然需要一個(gè)強(qiáng)大的搜索算法給予支持。大家普遍相信，Google 從一個(gè)研究型項(xiàng)目迅速崛起為世界范圍內(nèi)最受歡迎的搜索引擎，這在很大程度上歸功于它的 RageRank 網(wǎng)頁(yè)排名機(jī)制及其收斂加速算法的進(jìn)一步發(fā)展。這種基于鏈的網(wǎng)頁(yè)排名的巧妙之處在于它把整個(gè)互聯(lián)網(wǎng)當(dāng)作了一個(gè)整體的結(jié)構(gòu)來(lái)看待，這無(wú)意識(shí)的符合了系統(tǒng)論和整

10、體的觀點(diǎn)。與以前的相比，以前的信息檢索大多把每一個(gè)網(wǎng)頁(yè)當(dāng)作獨(dú)立的個(gè)體對(duì)待，很多人當(dāng)初只看重頁(yè)面內(nèi)容和查詢關(guān)鍵詞之間的相關(guān)性，忽略了頁(yè)面之間的關(guān)系。當(dāng)前，Google 搜索引擎比最初復(fù)雜、完善了許多。從系統(tǒng)的觀點(diǎn)上來(lái)看，據(jù) Google 最近檢測(cè)，互聯(lián)網(wǎng)上獨(dú)立頁(yè)面的數(shù)量超過(guò)了 1 萬(wàn)億個(gè)并且發(fā)現(xiàn)互聯(lián)網(wǎng)上每天新增加數(shù)十億個(gè)網(wǎng)頁(yè)1。Google 互聯(lián)網(wǎng)搜索基礎(chǔ)架構(gòu)團(tuán)隊(duì)的軟件工程師杰西阿爾帕特和尼桑哈賈吉在博客中寫(xiě)道， “我們沒(méi)有索引這 1 萬(wàn)億個(gè)網(wǎng)頁(yè)中的每個(gè)頁(yè)面因?yàn)樵S多頁(yè)面都彼此相似，或代表自動(dòng)生成的內(nèi)容，這些對(duì)用戶沒(méi)多大意義。但令我們驕傲的是，我們擁有最完整的索引數(shù)據(jù)庫(kù)。我們的目標(biāo)是索引全球的數(shù)據(jù)

11、。”由此可以看出，當(dāng)前的 Google 搜索引擎在信息采集上處于領(lǐng)先地位，其得到的龐大索引數(shù)據(jù)庫(kù)不單純追求網(wǎng)頁(yè)鏈接的數(shù)量，同時(shí)采取了一些很有力的篩選和過(guò)濾措施。這也使得基于鏈分析的網(wǎng)頁(yè)排序(PageRank)受人為控制因素大為減少或者說(shuō)是微不足道的，并且響應(yīng)速度快同時(shí)也不影響網(wǎng)頁(yè)排名的質(zhì)量。在武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文2學(xué)術(shù)界, 這個(gè)網(wǎng)頁(yè)排序算法被公認(rèn)為是文獻(xiàn)檢索中最大的貢獻(xiàn)之一，并且被很多大學(xué)引入了信息檢索課程的教程。因此，對(duì)網(wǎng)頁(yè)排序算法(PageRank 算法)的分析、探索、研究和應(yīng)用具有重大的現(xiàn)實(shí)意義。1.2 PageRank 簡(jiǎn)介 PageRank 算法是由 Google

12、的創(chuàng)始人提出的，現(xiàn)在基于這一思路的各種變種已被所有大型搜索引擎采用。該算法為每個(gè)頁(yè)面都賦予了一個(gè)指示頁(yè)面重要程度的評(píng)價(jià)值。網(wǎng)頁(yè)的重要性由指向該網(wǎng)頁(yè)的所有其他網(wǎng)頁(yè)的重要性和這些網(wǎng)頁(yè)中所包含的鏈接數(shù)求得。理論上，PageRank（以 Google 創(chuàng)始人之一 Larry Page命名）計(jì)算的是某個(gè)人在任意次鏈接點(diǎn)擊之后到達(dá)某一網(wǎng)頁(yè)的可能性。如果某網(wǎng)頁(yè)擁有來(lái)自其他比較熱門(mén)網(wǎng)頁(yè)的外部回指鏈接越多，人們無(wú)意間訪問(wèn)該網(wǎng)頁(yè)的可能性也就越大。當(dāng)然，如果用戶始終不停地點(diǎn)擊，那么他們終將到達(dá)每一個(gè)網(wǎng)頁(yè)，但是大多數(shù)人在瀏覽一段時(shí)間之后都會(huì)停止點(diǎn)擊。為了反映這一情況，PageRank 還使用了一個(gè)值為 0.85 的阻

13、尼因子(damping factor)，用以指示用戶持續(xù)點(diǎn)擊每個(gè)網(wǎng)頁(yè)中鏈接的概率為 85%。在計(jì)算網(wǎng)站排名時(shí)， Pagerank 會(huì)將網(wǎng)站的外部鏈接數(shù)考慮進(jìn)去。并不 是說(shuō)一個(gè)網(wǎng)頁(yè)的外部鏈接數(shù)越多其 頁(yè)面評(píng)價(jià)值就越高， 若是這樣的情形，一個(gè)網(wǎng)站 只需要盡可能獲得最多的外部鏈接就可以了，有這種想法是錯(cuò)誤的。 Google 看重一個(gè)網(wǎng)頁(yè)上的外部鏈接數(shù) ，但并不意味著你 能夠不求策略地與任何網(wǎng)站建立 鏈接。這是由于 Google 并不是僅僅由網(wǎng)頁(yè)的外部鏈接數(shù)來(lái)決定其等級(jí) ，也會(huì)考慮其質(zhì)量。 在此基礎(chǔ)上也會(huì)考慮外部鏈接的數(shù)量。例如，對(duì)一個(gè)有一定 網(wǎng)頁(yè)評(píng)價(jià)值的網(wǎng)頁(yè) X，若網(wǎng)頁(yè) Y 是它的唯一的外部鏈接，那

14、么 Google 就認(rèn)為網(wǎng)頁(yè) X 將網(wǎng)頁(yè) Y 視做它最好的一個(gè)外部鏈接，從而會(huì)給你的網(wǎng) 頁(yè) Y 更多的分值?？墒牵绻W(wǎng)頁(yè) X 上已經(jīng)有 39 個(gè)外部鏈接，那么 Google 就認(rèn)為網(wǎng)頁(yè) X 只是將你的網(wǎng)頁(yè)視做它第 40 個(gè)好的網(wǎng)站。因而你的外部鏈接站點(diǎn)上的外部鏈接數(shù)越多，你所能夠得到的分值反而會(huì)越低。 可見(jiàn) Google 搜索引擎排序是一個(gè)復(fù)雜問(wèn)題，比最初復(fù)雜、完善 的多，但是網(wǎng)頁(yè)排名在 Google 所有算法中依然 占有重要位置。當(dāng)前幾乎所有主要的網(wǎng)頁(yè)搜索引擎都以鏈分析來(lái)改進(jìn)搜索結(jié)果，PageRank武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文3機(jī)制首當(dāng)其沖。這對(duì)研究線性代數(shù)的學(xué)者來(lái)說(shuō)的確是一件

15、興奮的事，因?yàn)閷?duì)于網(wǎng)頁(yè)超鏈結(jié)構(gòu)的運(yùn)用是依據(jù)矩陣?yán)碚摰幕A(chǔ)而構(gòu)建的。鏈分析及其底層的線性代數(shù)使網(wǎng)頁(yè)搜索產(chǎn)生革命性巨變，一些基于冪法的收斂加速算法研究變得異?；钴S，這令 1998 年之前的預(yù)鏈分析搜索在今天如此精準(zhǔn)高效搜索面前黯然失色。1.3 本文的主要內(nèi)容和結(jié)構(gòu)安排當(dāng)前的搜索引擎不得不做的三件事：1. 利用爬蟲(chóng)程序搜集頁(yè)面文檔，有時(shí)可能涉及針對(duì)特定網(wǎng)頁(yè)的抓取2-在互聯(lián)網(wǎng)上先從一小組網(wǎng)頁(yè)開(kāi)始，然后再根據(jù)網(wǎng)頁(yè)內(nèi)的鏈接逐步追蹤其他的網(wǎng)頁(yè)。2. 根據(jù)步驟 1 進(jìn)行必要處理，為全文索引建立數(shù)據(jù)庫(kù)，以便對(duì)相關(guān)的關(guān)鍵字或關(guān)鍵詞進(jìn)行高效檢索。3. 根據(jù)某種評(píng)價(jià)方法如 PageRank 排名機(jī)制，對(duì)給定的查詢條件

16、為網(wǎng)頁(yè)進(jìn)行評(píng)價(jià)，以便能在返回查詢結(jié)果中將評(píng)價(jià)最高者排在最前面。本文將集中考慮第 3 步,即在假定索引數(shù)據(jù)庫(kù)已經(jīng)建立的基礎(chǔ)上研究頁(yè)面的等級(jí)排序問(wèn)題。這也有利于集中于其核心思想的研究。本文所做工作主要分成三個(gè)部分：第一部分是在介紹 PageRank 基礎(chǔ)知識(shí)的前提下，建立 PageRank 的基本模型，同時(shí)將針對(duì)各種不利情形對(duì) PageRank 矩陣進(jìn)行修正。第二部分主要針對(duì)第一部分提出的修正矩陣使用一定的數(shù)值解法解決 PageRank 的排序問(wèn)題，在此基礎(chǔ)上給出加速收斂的方法。第三部分是應(yīng)用，將針對(duì)一現(xiàn)實(shí)中的網(wǎng)絡(luò)驗(yàn)證第二部分提出的修正方法的合理性并給出收斂加速的效果圖。本文結(jié)構(gòu)安排如下，第二章介

17、紹 PageRank 的基本概念以及基本的PageRank 模型，包括它涉及到的基本概念、定義、定理和性質(zhì)。第三章介紹 PageRank 問(wèn)題的求解方法。給出了解決 PageRank 排序的數(shù)值方法冪法及其偽碼。第四章在基于冪法的理論基礎(chǔ)之上,給出一種加速收斂的外推法-The vector-algorithm 及其偽碼。第五章是應(yīng)用，結(jié)合一現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)進(jìn)行測(cè)試。包括對(duì)模型的驗(yàn)證以及收斂加速的分析。最后是對(duì)本文的總結(jié)與展望。武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文42 基本的 PageRank 模型21 PageRank 的基本概念 CAB圖 2-1 簡(jiǎn)化網(wǎng)絡(luò)結(jié)構(gòu)圖 網(wǎng)頁(yè)級(jí)別(PageRank

18、):2001 年 9 月被授予美國(guó)專利，專利人是 Google 創(chuàng)始人之一拉里佩奇 PageRank 專利人拉里佩奇（Larry Page） 。因此，PageRank里的 page 不是指網(wǎng)頁(yè)，而是指佩奇，即這個(gè)等級(jí)方法是以佩奇來(lái)命名的。它是Google 排名運(yùn)算規(guī)則（排名公式）的一部分，是 Google 用于用來(lái)標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)/重要性的一種方法，是 Google 用來(lái)衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。在揉合了諸如 Title 標(biāo)識(shí)和 Keywords 標(biāo)識(shí)等所有其它因素之后，Google 通過(guò)PageRank 來(lái)調(diào)整結(jié)果，使那些更具“等級(jí)/重要性”的網(wǎng)頁(yè)在搜索結(jié)果中另網(wǎng)站排名獲得提升，從而提高搜

19、索結(jié)果的相關(guān)性和質(zhì)量。分?jǐn)?shù)越高說(shuō)明該網(wǎng)頁(yè)越受歡迎（越重要） 。網(wǎng)絡(luò)結(jié)構(gòu)圖(Structure Of The Web)：由頁(yè)面作為圖結(jié)點(diǎn)，頁(yè)面之間的鏈接作為邊的有向圖。轉(zhuǎn)移概率矩陣：矩陣各元素都是非負(fù)的，并且各行元素之和等于 1，各元素用概率表示，在一定條件下是互相轉(zhuǎn)移的，故稱為轉(zhuǎn)移概率矩陣。武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文5分?jǐn)?shù)(Score)：我們用一個(gè)頁(yè)面所獲得分?jǐn)?shù)的高低作為評(píng)價(jià)一個(gè)頁(yè)面質(zhì)量好壞的標(biāo)準(zhǔn)，并且這個(gè)重要性的分?jǐn)?shù)總是非負(fù)的實(shí)數(shù)。一個(gè)頁(yè)面的得分來(lái)源于其他頁(yè)面對(duì)這個(gè)頁(yè)面的鏈接，如圖 2.1 頁(yè)面 C 的得分來(lái)源于 A、B。前鏈(Forward links): 頁(yè)面 P 得到另一個(gè)

20、頁(yè)面 Q 的鏈接，則 Q 是 P 的前鏈，對(duì)于結(jié)點(diǎn) P 而言，前鏈數(shù)為 P 的出度數(shù)(Outdegrees)。如圖 2.1 有 C、B 為 A 的前鏈,A 的出度為 2。背鏈(Backlinks): 頁(yè)面 P 給予另一個(gè)頁(yè)面 Q 的鏈接，則 P 是 Q 的背鏈，對(duì)于結(jié)點(diǎn) Q 而言，背鏈數(shù)為 Q 的入度數(shù)(Indegrees)。如圖 2.1 有 A、B 為 C 的背鏈。懸點(diǎn)(Dangling Nodes):不含出度的頁(yè)面結(jié)點(diǎn)，如圖 2.1 有 C 為懸點(diǎn)。2.2 PageRank 的基本模型如果我們把整個(gè)因特網(wǎng)絡(luò)看作一個(gè)大型的拓?fù)浣Y(jié)構(gòu)圖，網(wǎng)頁(yè)頁(yè)面看作節(jié)點(diǎn)，頁(yè)面之間的超鏈接看作有向邊，于是就形成的

21、了一個(gè)巨大的有向圖 G。如何進(jìn)行網(wǎng)頁(yè)等級(jí)排序，最初 Google 的兩個(gè)創(chuàng)始人拉里佩奇 (Larry Page )和謝爾蓋布林 (Sergey Brin) 把這個(gè)問(wèn)題轉(zhuǎn)化為二維矩陣相乘的問(wèn)題，并且用迭代的方法解決。他們提出的 PageRank 模型用于具有超鏈結(jié)構(gòu)的網(wǎng)絡(luò)的頁(yè)面排序。設(shè),邊表示網(wǎng)頁(yè)存在 的超鏈接，考慮在有向圖 G 上隨機(jī)游走的馬, u vGuvuv可夫鏈12，一個(gè)用戶在時(shí)刻訪問(wèn)了頁(yè)面。在下一時(shí)刻該用戶通過(guò)隨機(jī)選擇ku上的某個(gè)超鏈接，訪問(wèn)到了的某個(gè)指向的頁(yè)面，其中。另uuiv |ivv uv一方面，在時(shí)刻，訪問(wèn)者在的機(jī)率是。轉(zhuǎn)移概率矩1k |ivv uv1/deg( )u陣由 G

22、的鏈接情況定義，即當(dāng)存在超鏈接從網(wǎng)頁(yè)鏈接到的時(shí)候，P1/deg( )ijpi其余的，PageRank 即為此馬可夫鏈的平穩(wěn)分布。設(shè)頁(yè)面 的出度記為0ijp i，則矩陣用于描述有向圖 G 中頁(yè)面 與之間的傳輸，并且有：deg( )1i ()ijPpij武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文61deg( )0ijip, deg(i )0 , deg(i )=0于是構(gòu)造了一個(gè)以轉(zhuǎn)移概率矩陣為特征的馬可夫鏈。由馬可夫鏈遍歷定理(ErgodicTheorem)3,只有當(dāng)轉(zhuǎn)移矩陣是非周期不可約的情況下才有唯一的平穩(wěn)P分布。此非周期不可約條件保證了穩(wěn)定向量 存在，其值與初始值的選取無(wú)關(guān)。v通過(guò)計(jì)算該馬可夫鏈

23、的穩(wěn)定向量 得到 PR 值(PageRank 值)，并且收斂速度取v決于 PageRank 矩陣的第二特征值的大小4。2ABCDABCDABCD圖 2-2 理想圖 圖 2-3 存在懸點(diǎn) 圖 2-4 存在子圖根據(jù)轉(zhuǎn)移矩陣的定義，從上圖 2-2 可得到, , Pdeg( )1A deg( )2B ,有deg( )2C deg()1D (2-1)00101100221100220010P從上圖 2-3 可得到,deg( )1A deg( )3B deg( )2C deg()0D (2-2)001011103331100220000P從上圖 2-4 可得到,deg( )1A deg( )1B deg(

24、 )1C deg()1D 武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文7 (2-3)0100100000010010P若矩陣為式(2-1)的形式，我們發(fā)現(xiàn)有特征值 1,事實(shí)上取,則有PP(1,1,1,1)e 。Pee定義定義 2.2 一個(gè)稀疏矩陣稱為列隨機(jī)方矩陣(Column-Stochastic matrix)，如果該矩陣中所有的元素均為非負(fù)的，且每一列的總和均為 1。不包含懸點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)圖得到的轉(zhuǎn)移概率矩陣的轉(zhuǎn)置是列隨機(jī)()TTijPp矩陣，我們只需要證明下面的命題。命題命題 2.2 每一個(gè)列隨機(jī)方陣都有特征值 1。證明:設(shè)是列隨機(jī)矩陣， 為全 1 的 n 維列向量。則對(duì)有,所TnnPeTnnP

25、nnP ee以 1 是的特征值，因此 1 也是的特征值。nnPTnnP下面我們用來(lái)表示列隨機(jī)矩陣的特征值為 1 的特征向量空間。以()TL PTP下均表示由網(wǎng)絡(luò)結(jié)構(gòu)圖得到的轉(zhuǎn)移概率矩陣的轉(zhuǎn)置。同時(shí)將會(huì)發(fā)()TTijPpP現(xiàn)，如果對(duì)進(jìn)行必要的修正(見(jiàn) 2.4 節(jié))后，將滿足馬可夫鏈遍歷定理和列TPTP隨機(jī)性，此時(shí)必存在對(duì)應(yīng)于主特征值 1 的穩(wěn)定特征向量 ，此主特征向量即可v作為 PageRank 向量5。定理定理 2.2 (Gerschgorins 定理) 設(shè)，則的每一個(gè)特征值必屬于下*()ijn nAaA述某個(gè)圓盤(pán)之中： ()1|niiijjj iaa1,2,in證明 設(shè)為的任意一個(gè)特征值，為

26、對(duì)應(yīng)的特征向量，即Ax (2-4)()0IA x記及，,所以從式(2-4)的第 個(gè)方程12( ,)0Tnxx xx| max |ikkxx0ix i武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文81()niiiijjjj iaxa x以及 ()，有|/| 1jixx ji , .|iiijj iaa|/|jiijj ixxa這說(shuō)明屬于復(fù)平面上以為圓心、為半徑的一個(gè)圓盤(pán)。iia|ijj ia定理的證明，不僅指出了的每一個(gè)特征值必屬于的一個(gè)圓盤(pán)中，而且指出，若一個(gè)特征向量的第個(gè)分量最大，則對(duì)應(yīng)的特征值一定屬于第個(gè)圓盤(pán)中。更重要的一點(diǎn)，可以發(fā)現(xiàn)列隨機(jī)矩陣的特征值均不大于 1，所以列隨機(jī)矩陣的TPTP特征值可

27、以表示為, 其中231,n 231 | |,n2.3 存在的問(wèn)題由于網(wǎng)絡(luò)的復(fù)雜性，導(dǎo)致從某些網(wǎng)絡(luò)結(jié)構(gòu)圖中得到的轉(zhuǎn)移矩陣得不到一P個(gè)穩(wěn)定的特征向量(PageRank eigenvector)。下面主要討論兩種情形：1.存在懸點(diǎn);2.得到的主特征向量不唯一。2.3.1 懸點(diǎn)(Dangling Nodes)如果一個(gè)網(wǎng)絡(luò)中出現(xiàn)懸點(diǎn)，這種情況也是很常見(jiàn)的，如圖 2-3 將導(dǎo)致轉(zhuǎn)移矩陣的某一列或某幾列全 0。此時(shí)矩陣是列子隨機(jī)的，也就是的各列元TPTPTP素之和小于或等于 1。在這種情形下，必然會(huì)有所有的特征值小于或等于 1（由定理 2.2 得） 。可是，在存在懸點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)中，我們?nèi)匀豢梢杂猛瑯拥姆绞絹?lái)

28、處理排名問(wèn)題。相應(yīng)的列子隨機(jī)陣必定有一個(gè)非負(fù)的特征值滿足,其相應(yīng)的1特征向量 x 是非負(fù)的(稱為 Perron 特征向量)6，此特征向量符合頁(yè)面排序的要求。2.3.2 主特征向量空間不是一維的()TL P我們希望矩陣的主特征向量空間是一維的，這樣就可以標(biāo)準(zhǔn)化為唯一的TP所需排名得分向量 滿足。但并不一定能滿足這個(gè)要求，如上圖 2-4 x1ix 得到的矩陣,是二維的，其中可行的基向量為;TP()TL P11 1( ,0,0)2 2x ;但與的任意線性組合均屬于,例如：21 1 1 1( , )4 4 4 4x 1x2x()TL P武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文9;，可見(jiàn)不能明確的得到一個(gè)

29、穩(wěn)11121 1 1 1( , , )333 3 6 6xx12215511(,)3312 12 12 12xx定的 PageRank 向量。當(dāng)然這種情形并非偶然，如果某個(gè)網(wǎng)絡(luò)結(jié)構(gòu)圖是非連通圖，即由一些子G連通圖構(gòu)成，則有。12,nG GGdim( ( )L Pn不訪設(shè)圖對(duì)應(yīng)于矩陣,子圖對(duì)應(yīng)于子矩陣，得到如下轉(zhuǎn)移矩陣GPiGiP (2-5)1200000000nPPPP設(shè)總頁(yè)面數(shù)為，對(duì)于矩陣中的每個(gè)的子矩陣是列隨機(jī)的，因此mTP*iimmTiP存在一個(gè)向量,。很容易得到一組線性無(wú)關(guān)的特征向量,()TiixL P1ijx iX,如下：1in ，1100 xX2200 xX滿足0000TTiiiP

30、 XPXx可知,又線性無(wú)關(guān)，所以的維數(shù)至少為。()TiXL PiX()TL Pn所以不能得到一個(gè)確定的 PageRank 向量,。()TxL P1ix 2.4 對(duì)上述問(wèn)題的修正為了避免上述的兩個(gè)問(wèn)題，需要對(duì)原先定義的矩陣做一些修改，以滿足TPPageRank 向量的唯一性。武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文102.4.1 對(duì)出現(xiàn)懸點(diǎn)的修正如果網(wǎng)絡(luò)結(jié)構(gòu)圖中出現(xiàn)懸點(diǎn)，則的某些列是全 0 的，使得轉(zhuǎn)移矩陣不PP滿足列隨機(jī)。對(duì)這個(gè)問(wèn)題有幾種修正方法，最常用的是用另一個(gè)矩陣代替。PP設(shè)概率向量，為總頁(yè)面數(shù)，滿足且；向12(,)Tmmww wwRm0w1iw 量,滿足，( )miqqR1,0,ijiq

31、為懸點(diǎn)其他有 。TPPqw其中附加的矩陣是可行的，如果某個(gè)用戶搜索到了為懸點(diǎn)的網(wǎng)頁(yè)，此時(shí)已Tqw經(jīng)不存在其他頁(yè)面的超鏈接，則假定用戶以概率向量來(lái)跳轉(zhuǎn)到其他頁(yè)面。一w般可設(shè),即以相同的概率跳轉(zhuǎn)?？芍仃囀橇须S機(jī)的，因此有特征值1iwmTP為 1 的 PageRank 向量。又由定理 2.2可知，的特征值均不大于 1。TP 2.4.2 對(duì)的修正dim( ()2TL P如果圖又出現(xiàn)多個(gè)子圖，則矩陣可約(reducible)，即矩陣特征值GiGTPTP為 1 的特征向量不是一維的。4中給出了這種情形的修正，此時(shí)被另一矩陣TP代替TP(1),TPPEEew其中阻尼因子，在 Google 中常取 0.85

32、7，為概率向量同上，又稱0,1w為個(gè)性化向量(Personalization Vector)，又可表示從一子鏈接圖跳到另一子鏈w接圖的概率。此時(shí)矩陣非負(fù)不可約，列隨機(jī)且存在 PageRank 向量。因?yàn)?TPTv.(1)(1) ()(1)TTPePeew ePee w eeee同時(shí)我們發(fā)現(xiàn)為完全稠密矩陣。TP定理定理 2.4.1 修正矩陣 的第二特征值.(1) ,TTTPPEEew2|武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文11定理定理 2.4.2 若矩陣具有至少 2 個(gè)不可約的子集，則修正矩陣的第二特TPTP征值為.以上兩個(gè)定理的證明可參見(jiàn) 8。3 對(duì) PageRank 問(wèn)題的求解方法在一些工

33、程、物理問(wèn)題中，通常只需要求出矩陣的按模最大的特征值（稱為的主特征值）和相應(yīng)的特征向量，對(duì)于解這種特征值問(wèn)題，應(yīng)用冪法A(Power Methord)是合適的。3.1 冪法冪法是一種計(jì)算矩陣主特征值(矩陣按模最大的特征值)及對(duì)應(yīng)特征向量的A數(shù)值迭代方法，它最大的優(yōu)點(diǎn)是方法簡(jiǎn)單，對(duì)于稀疏矩陣較合適，但有時(shí)收斂的速度很慢。設(shè)實(shí)矩陣有一個(gè)完全的特征向量組，其特征值為，相應(yīng)()ijnAa12,n 的特征向量為。已知的主特征值是實(shí)根，且滿足條件12,nx xx123| | |,n冪法的基本思想是任取一個(gè)非零的初始向量，由矩陣構(gòu)造一向量序列0vA102210110kkkvAvvAvA vvAvAv稱為迭代

34、向量。由假設(shè)，可表示為0v (設(shè)),01 122nnva xa xa x10a 于是0v01 11222kkkknnnA vaxaxax ,11 11111 12(/)()nkkkiikia xaxa x武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文12其中。由假設(shè) ，故 ，112(/)nkkiiiax1|/| 1i(2,3, )in0k()k 從而1 11limkkkva x這說(shuō)明序列越來(lái)越接近的對(duì)應(yīng)于的特征向量。1kkvA下面考慮主特征值的計(jì)算。用表示的第 個(gè)分量，則1()kivkvi (3-1)1111111()()()()()()kiikikiikiva xva x故11()lim()kikk

35、ivv即兩相鄰迭代向量分量的比值收斂到主特征值。由式(3-1)知，的收斂速度由比值來(lái)確定， 越小收斂11() /()kikivv21/rr越快，但當(dāng)時(shí)收斂可能就很慢。21/1r3.2 在 PageRank 上的冪法通過(guò)計(jì)算該馬可夫鏈的穩(wěn)定向量 以決定 PR 值(PageRank 值)，根據(jù)第 2 章v得到的新的轉(zhuǎn)移矩陣，可知 PageRank 就是在這個(gè)所對(duì)應(yīng)的馬可夫鏈的平TPTP穩(wěn)分布，也即是的特征值 1 所對(duì)應(yīng)的特征向量 。有方程TPv (或).TTv PvTP vv3.2.1 初始優(yōu)化 PageRank 矩陣盡管冪法不總是很有效，但 Google 選擇其作為數(shù)值解法。主要出于兩點(diǎn)考慮：第

36、一，如果將冪法作用于矩陣，由于它是完全稠密的，必定影響冪法的TP收斂速度。但考慮其展開(kāi)形式，有 P(1)(1)TPEPew武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文13()(1)TTPqwew(1) )TPqe w則有冪法表達(dá)式( )k Tv(1)(1)(1) )kTkTTvPvPqe w(1)(1)(1)(1)kTkTkTTvPvqve w(1)(1)(1)(1)()kTkTkTTvPvqve w (3-2)(1)(1)(1)kTkTTvPvqw其中為概率向量,通常取初值。(1)kTv(0)111(,)TTevmm mm寫(xiě)成如上式(3-2)的形式，很容易看出冪法作用于矩陣可以由向量-矩陣乘積TP

37、形式作用于大型稀疏矩陣實(shí)現(xiàn)，在此過(guò)程中無(wú)需構(gòu)造并存儲(chǔ)修正矩陣和，PPP極大的減少了存儲(chǔ)空間。盡管目前 Google 索引的頁(yè)面數(shù)量超過(guò) 82 億個(gè)頁(yè)面1，由于矩陣是極為稀疏的，每行中非零元素平均不超過(guò) 10 個(gè)同時(shí)有很多全零列,使P得冪法的收斂速度很快。由定理 2.4.2 知矩陣的次大特征值(1) TTPPE滿足（取 0.85） ，使得收斂很快，正因?yàn)槿绱?，?22210.851Lawrence Page 和 Sergey Brin 的報(bào)告中指出成功迭代的次數(shù)在 50 到 100 步16。此外，冪法在每步迭代中只須存儲(chǔ)一個(gè)向量，也就是當(dāng)前迭代向量。這有別于像 BiCGStab 等其他方法，減少

38、了空間存儲(chǔ)量。雖然說(shuō) PageRank 排序的基本思想很簡(jiǎn)單，但其背后有比較完善的矩陣?yán)碚撟鳛橹?，很多微妙的?wèn)題潛藏在暗處，如個(gè)性化計(jì)算，加速收斂，靈敏度分析及運(yùn)行的時(shí)間與空間復(fù)雜度估計(jì)等等。3.2.2 冪法的偽代碼Function =PowerMethod()()mvInitialize(,);(0)vw武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文14;1k Repeat;( )(1)(1)(1)k TkTkTTvvPvqw;( )(1)kkvv;1kkUntil ;4 冪法加速研究提高運(yùn)算效率從來(lái)都是一個(gè)誘人的話題，特別是對(duì)于 Google 搜索引擎面對(duì)如此巨大的索引數(shù)據(jù)，運(yùn)算效率更是一個(gè)不容

39、忽視的問(wèn)題。好的運(yùn)算速度很快就能返回結(jié)果,使客戶滿意度大為提高同時(shí)也提高了該領(lǐng)域的競(jìng)爭(zhēng)力。在冪法的理論基礎(chǔ)之上，之前有許多人對(duì)冪法加速收斂的問(wèn)題進(jìn)行了研究，如原點(diǎn)平移法，Rayleigh 商加速法,外推法(Extrapolations Methods)包括著名的 AitKen -過(guò)程等。24.1 外推法外推法利用過(guò)去和現(xiàn)在已知其構(gòu)成規(guī)律的動(dòng)態(tài)統(tǒng)計(jì)數(shù)列向未來(lái)的延伸的方法。有用的外推規(guī)則有如下特性：設(shè)一序列收斂到極限 ，通過(guò)一外推方程得到一( )()nxv( )()nx( )( ):()()nnTxy個(gè)新的序列同樣收斂于極限 ，但序列比序列收斂的更快，即( )()nyv( )()ny( )()nx

40、有( )( )lim0nnnyvxv有許多外推方程被提出，下面將介紹一種很好的外推方法被稱( )( ):()()nnTxy為 The vector -algorithm71214。武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文154.1.1 The vector -algorithm外推算法 The vector -algorithm 由 Wynn12首次提出，由 Graves-Morris13證明。在一定條件下，通過(guò)這種外推規(guī)則，可以從原始序列得出一新的序列收斂于同一極限值，并且使序列收斂的更快。設(shè)為原始向量序列收斂于極限值，The vector algorithm 的外推規(guī)則( )()nxmvR如

41、下：； ；( )10n( )( )0nnx( )0,1,;nmnxR ；( )( )(1)112( )nnnkkknk0,1,;1,2,nk其中 .( )(1)( )nnnkkk可以看出,當(dāng)序列為標(biāo)量時(shí)，取即可得出著名的 AitKen -過(guò)程1417( )()nx1k 218。 ， (4-1)( )2n(2)(1)(1)( )(1)(2)(1)( )()()2nnnnnnnnxxxxxxxx考慮兩種情形加速方式：標(biāo)量法：對(duì)矩陣運(yùn)用冪法可得到一收斂于主特征值 1 的標(biāo)(1) TTPPE量序列，因此可以用上面的 AitKen -過(guò)程(式(2-4)將序列映射到( )k2( )k序列，使其更快的收斂于

42、主特征值 1。( )k向量法：對(duì)矩陣運(yùn)用冪法同樣可得到一收斂于主特征向量(1) TTPPE的向量序列，運(yùn)用式（4-2）可以將序列映射到向量序列，使v( )kv( )kv( )kv其更快的收斂于主特征向量 。v設(shè)是一向量序列。當(dāng)時(shí)，有如下表示形式( )()nx1k ，( )10n( )( )0nnx，( )( )( )(1)001122( )( )00nnnnnn( )(1)( )(1)( )000nnnnnxx武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文16， (4-2)( )( )(1)122( )1nnnnx( )(1)( )111nnn4.1.2 The vector -algorithm 偽

43、代碼基于上面的外推規(guī)則，下面給出取時(shí)向量法的 The vector-algorithm1k 偽代碼：Function = Vector_Algorithm_2(,)(*)x(2)kx(1)kx( )kx；(2)(1)kkpxx(1)( )kkqxx ， ( , )ppp p( , )qqq q(*)(1)(,)kpqxxpq pqReturn (*)xFunction =Accel_PowerMethod()vInitialize(,，);(0)vw(0)y;1k ( )(1)(1)(1)k TkTkTTvvPvqw1kkRepeat;( )(1)(1)(1)k TkTkTTvvPvqw=Ve

44、ctor_Algorithm_2(,)( )ky( )kv(1)kv(2)kv;(2)(1)kkvv;(1)( )kkvv武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文17;1kk;( )(1)kkyyUntil ;Return ;( )kvy5 應(yīng)用5.1 對(duì)簡(jiǎn)化的網(wǎng)絡(luò)進(jìn)行等級(jí)分析在 2.2 節(jié)中給出了如下的三個(gè)簡(jiǎn)化的網(wǎng)絡(luò)鏈接圖，可以看出很有代表性，圖2-2 是很理想的情形，從任一頁(yè)面結(jié)點(diǎn)均可以通過(guò)有限步跳到任意其它任一頁(yè)面結(jié)點(diǎn)處。圖 2-3 存在懸點(diǎn) D，此時(shí)當(dāng)用戶到達(dá)頁(yè)面 D 時(shí)，將不存在任何其它的頁(yè)面鏈接。圖 2-4 存在子網(wǎng)絡(luò)，AB，CD 分別構(gòu)成一個(gè)子網(wǎng)?，F(xiàn)實(shí)中的大型網(wǎng)絡(luò)超鏈構(gòu)成的有向圖均

45、可由這三個(gè)簡(jiǎn)化圖復(fù)合。應(yīng)用冪法易得表 5-1 的三個(gè)簡(jiǎn)化圖各結(jié)點(diǎn)的頁(yè)面等級(jí)(PageRank)得分。ABCDABCDABCD圖 5-1 理想圖 圖 5-2 存在懸點(diǎn) 圖 5-3 存在子圖表 5-1 簡(jiǎn)化圖的等級(jí)圖 結(jié)點(diǎn)ABCD圖 5-102991020010399301015圖 5-202788007150371002788圖 5-302500025000250002500武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文18圖 5-1 中結(jié)點(diǎn) A 的的分?jǐn)?shù)來(lái)自于 B、C，但可以看出 A 把票均投給了 C，而 C只是投了一半的票給 A，從這點(diǎn)也可以推出結(jié)點(diǎn) C 的分?jǐn)?shù)比 A 高。圖 5-2 發(fā)現(xiàn)B 沒(méi)有來(lái)

46、自任何結(jié)點(diǎn)的投票，但從表 5-1 可以看出其等級(jí)并不為零而是0.0715，這樣處理合理的理由是由于用戶行為的多樣性，對(duì)該網(wǎng)頁(yè)可能來(lái)自其它形式的了解或是一種盲目的跳轉(zhuǎn)，而有機(jī)會(huì)訪問(wèn)該網(wǎng)頁(yè)，或者說(shuō)訪問(wèn)者在訪問(wèn)頁(yè)面的時(shí)候會(huì)不通過(guò)頁(yè)面上的超鏈隨機(jī)跳轉(zhuǎn)到新的頁(yè)面。比如，當(dāng)用戶并不知道其它站點(diǎn)對(duì)百度的超鏈接，但該用戶知道其網(wǎng)址同樣可以訪問(wèn)該網(wǎng)頁(yè)。圖5-3 兩個(gè)子網(wǎng)存在訪問(wèn)的平衡性，也可推出等級(jí)是相同的?？梢?jiàn)這種基于鏈接的PageRank 頁(yè)面等級(jí)排序是合理的。5.2 對(duì)一個(gè)現(xiàn)實(shí)的復(fù)雜網(wǎng)絡(luò)進(jìn)行分析在 5.1 節(jié)驗(yàn)證了基于鏈接的 PageRank 頁(yè)面等級(jí)排序的合理性，下面通過(guò)一個(gè)現(xiàn)實(shí)的網(wǎng)絡(luò)來(lái)測(cè)試外推法的收斂

47、加速效果。測(cè)試數(shù)據(jù) .dat 來(lái)源于19。這個(gè)數(shù)據(jù)庫(kù)包含 4772 個(gè)網(wǎng)頁(yè)和 8965 個(gè)超鏈接，相關(guān)的鏈接情況如下圖 5-4。01000200030004000500060007000800090000500100015002000250030003500400045005000 圖 5-4 復(fù)雜網(wǎng)絡(luò)的鏈接圖武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文19為了體現(xiàn)出第 4 節(jié)中提供的外推法 The vector -algorithm 的效果，取阻尼因子=0.99 以降低收斂速率，使得外推法的作用更為明顯?；趫D 5-4 的現(xiàn)實(shí)網(wǎng)絡(luò)，圖 5-5 給出了這種情形下的冪法與外推法在

48、求其主特征值時(shí)的收斂情況。從圖中可以看出冪法與外推法在迭代數(shù)次后均變得很平穩(wěn)，其主特征值序列均收斂于 1。以誤差容限為時(shí)，冪法迭代 341 次后符合要求，外推法迭代 93310次后符合要求。圖 5-5 冪法與外推法的主特征值變化曲線同時(shí)為了更好的反映外推法對(duì)于阻尼因子的不同取值的加速效果，根據(jù)上面的偽代碼，在 matlab7.1，Pentium(R)4 CPU 3.00GHz ,0.99GB 內(nèi)存,Windows XP2環(huán)境上實(shí)現(xiàn),程序參見(jiàn)附錄。表 5-2 給出了此現(xiàn)實(shí)網(wǎng)絡(luò)的的冪法與外推法迭代次數(shù)與運(yùn)行時(shí)間。表 5-2 冪法與外推法的收斂測(cè)試表 Accel_PowerMothod 方法Powe

49、rMethod 方法主特征值迭代次數(shù)運(yùn)行時(shí)間(秒)主特征值迭代次數(shù)運(yùn)行時(shí)間(秒)0.991.0009936.17191.000534125.9531武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文200.981.0009976.43751.000619113.23440.971.0009976.34381.00061379.17190.961.0009815.29691.00061097.26560.951.0009714.53130.9997905.89060.941.0008634.00001.0007775.03130.931.0008573.59380.9998684.39060.921.000

50、9513.32811.0007613.92190.911.0008472.98441.0008553.51560.901.0008432.70311.0007513.21880.891.0009392.45311.0007473.01560.881.0009372.31251.0008432.75000.871.0008352.17191.0007412.70310.861.0008332.04691.0008372.28130.851.0008311.93751.0008352.15630.841.0008291.79691.0008332.0781圖 5-6 直觀地反映了冪法與外推法 Th

51、e vector -algorithm 在應(yīng)用中阻尼因子與迭代次數(shù)的關(guān)系比較?？梢钥闯鲈谟?jì)算大型網(wǎng)絡(luò)的等級(jí)排序中外推法 The vector -algorithm 在收斂加速中有優(yōu)異的表現(xiàn)。當(dāng)阻尼因子取值較小時(shí)，加速不明顯但仍然比傳統(tǒng)的冪法收斂的快；當(dāng)阻尼因子接近 1 時(shí)，有明顯地加速效果（迭代次數(shù)不超過(guò) 100）。武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文21圖 5-6 冪法與外推法的迭代曲線6 結(jié)語(yǔ)與展望Google 可以說(shuō)是當(dāng)今最成功的搜索引擎之一，而國(guó)內(nèi)對(duì) Google 的研究文章較少，對(duì)其核心技術(shù)進(jìn)行深入的剖析對(duì)于搜索引擎研究開(kāi)發(fā)具有極大的借鑒作用。作為商業(yè)的搜索引擎，其最核心的技術(shù)細(xì)節(jié)

52、是保密的，文中主要參考資料多為 Google 商業(yè)化之前設(shè)計(jì)者公開(kāi)發(fā)表的學(xué)術(shù)論文，因此在很大程度上增加了對(duì)這一技術(shù)介紹的難度。但是其排序算法的機(jī)理并沒(méi)有本質(zhì)的變化，PageRank技術(shù)仍然具有研究的價(jià)值。網(wǎng)頁(yè)排序 PageRank 是一項(xiàng)復(fù)雜的計(jì)算，其本質(zhì)就是求一個(gè)大型矩陣的主特征值（最大特征值）對(duì)應(yīng)的特征向量，而傳統(tǒng)的冪法是針對(duì)此類問(wèn)題求法中最有效的一種數(shù)值方法，由于網(wǎng)絡(luò)的復(fù)雜性，本文通過(guò)對(duì)轉(zhuǎn)移矩陣的分析和修P正，同時(shí)利用網(wǎng)絡(luò)結(jié)構(gòu)中的這種稀疏性，將冪法作用于矩陣（完全稠密）轉(zhuǎn)P化為由向量-矩陣乘積形式作用于大型稀疏矩陣實(shí)現(xiàn)，在此過(guò)程中無(wú)需構(gòu)造并P存儲(chǔ)修正矩陣和，極大的減少了存儲(chǔ)空間。由于矩陣

53、是極為稀疏的，每PPP武漢紡織大學(xué) 2010 屆畢業(yè)設(shè)計(jì)論文22行中非零元素平均不超過(guò) 10 個(gè)同時(shí)有很多全零行,使得冪法的收斂速度很快。在參考文獻(xiàn)20，通過(guò)最小二乘法對(duì)整體進(jìn)行外推計(jì)算得到的向量再次利用于原迭代中，而本文中給出的外推法僅僅檢測(cè)原迭代得到的向量序列，并將此序列外推成一個(gè)新的更快收斂的序列，同時(shí)考察這個(gè)新序列的終止條件。與20不同的是并不將新的序列運(yùn)用到原迭代中。當(dāng)然冪法中收斂速度除了和特征值有關(guān)，還與開(kāi)始的初始狀態(tài)有關(guān)，所以可以考慮優(yōu)化初始狀態(tài)使其更快地收斂。對(duì)于大型稀疏陣也可以做一定的矩P陣的初等變換，使懸點(diǎn)下沉即全零行下沉，再利用矩陣分塊的性質(zhì)可以減少存儲(chǔ)空間同時(shí)加速運(yùn)算速

54、度，具體的理論可以參考21。當(dāng)前有一些網(wǎng)站制作者通過(guò)站點(diǎn)鏈接和網(wǎng)站地圖等來(lái)提高站內(nèi)的 PageRank的反饋值。那么 Google 會(huì)不會(huì)對(duì)這樣的站點(diǎn)內(nèi)部鏈接投票值打折呢？而這樣做會(huì)不會(huì)影響這種基于鏈接的等級(jí)排序計(jì)算方法？因?yàn)檫@本身偏偏正是 PageRank工作的最基本的機(jī)理，所以有人認(rèn)為 PageRank 在 Google 排序算法中的作用已經(jīng)下降,可對(duì)于超過(guò) 82 億的頁(yè)面的偌大網(wǎng)絡(luò)鏈接圖，人為影響又能多大呢？剖析 PageRank 技術(shù)也并非我們的最終目的，關(guān)鍵在于通過(guò)對(duì) PageRank 排名算法的深入了解，以提出新的網(wǎng)絡(luò)搜索引擎排名機(jī)制以及研究并運(yùn)用一些新的運(yùn)算加速算法。 網(wǎng)絡(luò)變得越

55、來(lái)越龐雜，Google 的搜索效果也并非完美同時(shí)面臨同行的競(jìng)爭(zhēng)，排序算法的優(yōu)化還有很長(zhǎng)的路要走。參考文獻(xiàn)：1 CNET.Google 檢測(cè)獨(dú)立頁(yè)面量超 1 萬(wàn)億EB/OL.http:/ /07/28/00 3599068 .shtml,2008-07.2 Toby Segaran.集體智慧編程M.北京:電子工業(yè)出版社.2009.3 Grimmett G, Stirzaker D. Probability and random processesM.Oxford University Press.1989.4 李慶揚(yáng),王能超,易大義.數(shù)值分析(第 4 版)M.武漢:華中科技大學(xué)出版社.2006.5 Amy N.Langville and Carl D.Meyer.Deeper inside PageRankJ.Internet Mathem