4.4　PageRank算法

我們看一個實例，也就是PageRank算法。它最初被谷歌用來對用戶查詢的搜索結(jié)果進行排名。它產(chǎn)生數(shù)字來量化搜索結(jié)果在用戶所執(zhí)行的查詢中的重要程度。該算法誕生于20世紀(jì)90年代末，其設(shè)計者是斯坦福大學(xué)的兩位博士拉里·佩吉（Larry Page）和思爾格·布里恩（Sergey Brin），正是二人創(chuàng)立了谷歌公司。

我們先正式地定義最初設(shè)計PageRank算法時要求解的問題。

4.4.1　問題定義

每當(dāng)用戶在網(wǎng)絡(luò)搜索引擎中輸入查詢時，通常會得到大量的搜索結(jié)果。為了使搜索結(jié)果最終對用戶有用，使用一些標(biāo)準(zhǔn)對網(wǎng)頁進行排名是很重要的，排名的方式取決于正在使用的底層算法所定義的標(biāo)準(zhǔn)。用這種排名將所有搜索結(jié)果進行匯總，最后將匯總的搜索結(jié)果呈現(xiàn)給用戶。

4.4.2　實現(xiàn)PageRank算法

PageRank算法中最重要的部分是找到最佳方法來計算所返回的查詢結(jié)果中每個頁面的重要性。為了得出一個介于0和1的數(shù)字來量化特定頁面的重要性，該算法結(jié)合了以下兩個部分的信息：

• 與用戶輸入的查詢相關(guān)的信息：該部分根據(jù)用戶輸入的查詢來估計網(wǎng)頁內(nèi)容的相關(guān)程度。網(wǎng)頁的內(nèi)容直接取決于網(wǎng)頁的作者。
• 與用戶輸入的查詢無關(guān)的信息：該部分試圖量化每個網(wǎng)頁在其鏈接、瀏覽量和鄰域的重要性。這個部分很難計算，因為網(wǎng)頁是異構(gòu)的，很難提出可以適用于整個網(wǎng)絡(luò)的標(biāo)準(zhǔn)。

為了在Python中實現(xiàn)PageRank算法，首先，我們導(dǎo)入必要的包：

出于演示目的，假設(shè)我們僅分析網(wǎng)絡(luò)中的五個網(wǎng)頁，讓我們將這組頁面稱為myPages，它們一起位于一個名為myWeb的網(wǎng)絡(luò)中：

現(xiàn)在，我們把這些網(wǎng)頁隨機鏈接起來，從而模擬一個實際的網(wǎng)絡(luò)：

現(xiàn)在，我們繪制一幅圖來表示這些鏈接關(guān)系：

它創(chuàng)建了網(wǎng)絡(luò)的可視化表示，如圖4-8所示。

在PageRank算法中，網(wǎng)頁間的鏈接關(guān)系表示為一個矩陣，該矩陣被稱為轉(zhuǎn)移矩陣。轉(zhuǎn)移矩陣用一些算法來不斷更新，以捕獲網(wǎng)絡(luò)不斷變化的鏈接狀態(tài)。轉(zhuǎn)移矩陣的大小為n×n，其中n是節(jié)點數(shù)。矩陣中的數(shù)字是概率值，用來表示訪問者由于出站鏈接而在接下來的過程中訪問該鏈接的可能性。

在我們的示例中，圖4-8展示了我們擁有的靜態(tài)網(wǎng)絡(luò)。我們定義一個可用于創(chuàng)建轉(zhuǎn)移矩陣的函數(shù)（見圖4-9）。

請注意，此函數(shù)將返回網(wǎng)絡(luò)圖的轉(zhuǎn)移矩陣G。

我們?yōu)榻⒌撵o態(tài)網(wǎng)絡(luò)圖生成轉(zhuǎn)移矩陣（見圖4-10）。

注意，對于我們所創(chuàng)建的圖，轉(zhuǎn)移矩陣是5×5的矩陣。矩陣中的每一列對應(yīng)于圖中的一個節(jié)點。例如，第2列與第2個節(jié)點有關(guān)。訪問者從節(jié)點2導(dǎo)航到節(jié)點1或節(jié)點3的概率為0.5。請注意，轉(zhuǎn)移矩陣的對角線全是0，因為在我們的網(wǎng)絡(luò)圖中，沒有從節(jié)點到其自身的出站鏈接。在實際網(wǎng)絡(luò)中，卻可能會出現(xiàn)這種出站鏈接。

注意，轉(zhuǎn)移矩陣是稀疏矩陣。隨著節(jié)點數(shù)量的增加，其大多數(shù)值是0。