萬維網搜索算法的研究——從PageRank算法到WeightedIndegree算法.pdf

1、PageRank 算法是目前被廣泛應用的一種度量網頁重要性的方法，它根據網頁之間的鏈接結構來給每個網頁打分。從數學的角度來解釋，PageRank可以被看作是一個馬爾可夫隨機游走模型，依據網頁下一步的鏈接信息計算網頁的轉移概率。用馬氏鏈的平穩分布作為最終的Rank值給網頁排序。 受計算機象棋對弈算法設計中，一個很成功的策略“多看幾步”的啟發，我們改進和推廣了經典的PageRank算法，提出了N-step PageRank算法，它在

2、計算網頁的轉移概率時利用了網頁N步的鏈接信息。特別地，我們假定，如果網上沖浪者知道每個網頁的N步內的鏈接情況，那么在選擇下一步要瀏覽的網頁時他/她就可做出更好的選擇。經典PageRank算法是N-step PageRank算法N=1時的特殊情形。TREC標準數據集上的實驗表明，N-step PageRank算法能夠有效提高網頁搜索的精確度，MAP指標比經典的PageRank的提高超過15％． 經典PageRank算法和N-ste

3、p PageRank算法都是利用平穩分布來度量網頁的重要性。由于計算平穩分布實際上是計算矩陣的特征向量，計算復雜度很高，在萬維網搜索時海量數據信息使得計算的時間開銷很大。為了降低計算的復雜度，我們提出了一種更為簡單有效的鏈接分析方法——WeightedIndegree算法，與PageRank算法不同，它直接利用加權的入度給網頁排序。TREC標準數據集上的實驗表明，WeightedIndegree算法能夠大大降低算法的復雜性，同時能有效地