愛耍酷的Style

七月282008

【SEO】Google 的秘密- PageRank 徹底解說

星期一, 七月 28, 2008 13:06 | 9,332位訪客跟4,693 Bot看過

分類於： Google

Namazu 上的實際安裝實驗

為了使更簡單地推測上文描述的問題，PageRank 並不是非世界所有的web頁面而不能使用的考慮方法，即使是個人的利用方法也能實現。為了實現「Personalized PageRank」，針對在各種 UNIX 和 Windows 上運作的中小規模網站適用的全文檢索系統 Namazu 進行了實際安裝實驗。(關於Namazu可參考日語全文檢索引擎軟件列表。)

由於實驗能簡單地控制內存的使用量，並將最大特性值用1來考慮，所以將 Have liwala(1999)的想法做為基本的考慮方法。但是對 dangling pages 的處理有少許不同。固有矢量的計算內核使用了數值計算腳本 GNU Octave。所以基本的代碼編寫自己只用了一天就解決了。另外，從用 mknmz 編寫的索引不能直接計算 PageRank，而要事前準備表示鄰接關係的索引(鄰接列表)。這個也有可能被編入檢索者(Indexer)的主要部分。

以下表示了實際計算時間(單位：秒)。運行機器的配置為 PentiumII 400MHz x 2,內存512MB，Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp)，Octave-2.0.16(一般狀態分發物)。收斂精度(剩餘差矢量的L1規範)取了到1.0e-10,也許有些過分精確了。

文書數N     mknmz時間    準備時間   PageRank計算時間
============================================================
128          58          2          6
2,301       1, 575       46         214

49,604      15,975       478        5,872

因為沒用一些巨大的web頁群來做測試，所以實驗只停留在小規模的基礎上。雖然有這個難點,但從基本上可以瞭解與索引所花的時間相比，在很短的時間裡就可以計算 PageRank 的傾向吧。

因為 Namazu 自身中也有很多難題，所以並不寄予很大的奢望，但至少使用 10⁵ 程度(儘可能 10⁶)規模的web頁面群來實驗。從趨勢來看可以預想 N=10⁶ 的計算時間恐怕會發散開去，所以在 N=10⁶ 時，若是能夠討論把mknmz時間變成和comparable一樣的加速方法的話，對於Personalized PageRank 來說就十分實用了。作為參考，根據Page et al.(1998)，Google 對7500萬的URL的實際 PageRank 計算時間約是5小時。(2001年2月現在不明)。從這個角度來說，研究更加高效的加速法的餘地就十分得必要了吧。

計算實際運行時的使用內存最大也是10幾MB左右。如果是Haveliwala (1999)那樣的「吝嗇地作戰」的話，最大隻有O(3N+2)左右的內存使用量就做完了,不過 N 是 10^4-5 程度和內存的使用量連 N² 也放不進的話，其他的也只能勉強調諧了，所以以 O(5N+α) (α是疏鬆行列的非零成分數字，典型的是5-20N左右) 程度來編寫代碼。另外 N 是10³ 左右時，可以確認不壓縮疏鬆行列就在內存上使用冪乘法來計算，從速度面上來說是非常有利的。實測時速度為上述數字的6-7倍左右的。但遺憾的是，這個方法從內存的限制來看，儘可能地只使用2-3千頁以內。

此次我們使用了 Octave 分發附屬的「Tsurushi」,不過，正像大家知道的那樣，如果把 Octave 調諧的好的話，會戲劇性地提高完成的速度。Octave-2.1.x 和 ATLAS 的組合有時候根據情況甚至會使大規模行列乘法的運算速度提高10倍以上。

實驗的詳細結果請參照prnmz-1.0.tar.gz 中的文檔。

Personalized PageRank 的基本性質

人們經常會利用 MHonArc、latex2html 或者 PowerPoint 這樣的工具將文檔變成 HTML，針對這樣的人工製作的HTML鏈接群求 PageRank 的話，大部分頁面的得分幾乎都是一樣的(～1/N)。如果考慮鄰接行列，則大部分的成分是1，或者對角成分附近全部是1。因為這樣的推移概率行列的固有矢量成為(1,1,…,1)。

或是象 sitemap.html 一樣變成樹狀的情況下，分數會集中在sitemap.html中。就算佔據全體的9成也不算新奇。

從現在起能說的是，為了計算有意義的 PageRank，要儘可能地排除機械生成的鏈接關係。如果把鏈接關係看做是推薦關係的話更加容易認同了吧。