萬維網(wǎng)搜索算法的研究——從PageRank算法到WeightedIndegree算法.pdf

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

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

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