分塊式PageRank收斂算法及其改進(jìn).pdf

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

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

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

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