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

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

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

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