分塊式PageRank收斂算法及其改進.pdf

1、21世紀是信息化的世紀，人們無論是工作、學(xué)習(xí)、休閑、娛樂都已和因特網(wǎng)密不可分了。同時，各行各業(yè)的工作者們也選擇將自己的業(yè)務(wù)和信息發(fā)布于網(wǎng)上；信息數(shù)據(jù)化和數(shù)據(jù)網(wǎng)絡(luò)化已成為現(xiàn)代社會進步的標志。隨之而來的問題是，面對如此眾多的數(shù)據(jù)信息，人們該如何找到自己所需要的信息呢?最好的辦法是在因特網(wǎng)上使用一種可以按用戶意圖查找出他們所需要信息的網(wǎng)絡(luò)工具，搜索引擎技術(shù)便應(yīng)運而生了。搜索引擎技術(shù)的發(fā)展是隨著電子信息技術(shù)不斷進步而形成的信息數(shù)字化和數(shù)據(jù)網(wǎng)絡(luò)化

2、的必然產(chǎn)物。一個出色的搜索引擎能夠及時準確地向用戶提供所需要的信息，而要做到這點就需要一個快速，優(yōu)質(zhì)，高效的搜索算法予以支持。GOOGLE搜索引擎依靠其PageRank機制及收斂算法一直處于該領(lǐng)域的領(lǐng)先地位。而收斂算法的好壞尤為重要。它直接決定了得到最終PageRank向量的時空開銷，一個好的收斂算法可以使系統(tǒng)在較小的時空花費下得到最終向量值，從而使整個搜索引擎的效率都得到提高。目前為了能夠提高搜索引擎的效率，人們已經(jīng)進行了許多相關(guān)方面

3、的研究，其中有側(cè)重縮短收斂時間的，也有側(cè)重于提高查詢結(jié)果的準確性的。本文在前人研究的基礎(chǔ)上設(shè)計了一個旨在減少收斂算法運行時空開銷的分塊式PageRank收斂算法。該算法將網(wǎng)絡(luò)中的網(wǎng)頁劃分成不同的數(shù)據(jù)塊，然后計算塊內(nèi)PageRank和塊間PageRank值，最后再通過兩種PageRank值求得最終向量值。這個()用分塊的方式降低了矩陣的維數(shù)，有效減少了原算法中的0元素和0相乘計算，從而達到了減少系統(tǒng)運行時的時空開銷的目的，作者同時用實驗的

4、方式證明了該算法的優(yōu)越性。另一方面，在實驗中出現(xiàn)了一些與預(yù)期目標不相符合的情況：分塊算法的計算結(jié)果和一般算法相差很大；作者通過分析發(fā)現(xiàn)產(chǎn)生這種結(jié)果是因為分塊后塊間的鏈接被升級，從而使這些鏈接的原有網(wǎng)頁產(chǎn)生了PageRank值的損失。針對這個問題，作者對算法進行了改進：在分塊內(nèi)在有外鏈接的網(wǎng)頁之間建立虛擬鏈接，使這些網(wǎng)頁至少在鏈接數(shù)量上達到原來水平。通過實驗發(fā)現(xiàn)這種方法確實達到了保證收斂算法在時空花費優(yōu)越性的前提下減少結(jié)果產(chǎn)生偏差的目的。