资源描述：
《Computing PageRank using Power》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ComputingPageRankusingPowerExtrapolationTaherHaveliwala,SepandarKamvar,DanKlein,ChrisManning,andGeneGolubStanfordUniversityAbstract.WepresentanoveltechniqueforspeedingupthecomputationofPageRank,ahyperlink-basedestimateofthe“importance”ofWebpages,basedontheidea
2、spresentedin[7].TheoriginalPageRankalgorithmusesthePowerMethodtocomputesuccessiveiteratesthatconvergetotheprincipaleigenvec-toroftheMarkovmatrixrepresentingtheWeblinkgraph.Thealgorithmpre-sentedhere,calledPowerExtrapolation,acceleratestheconvergenceofthePowerM
3、ethodbysubtractingofftheerroralongseveralnonprincipaleigenvectorsfromthecurrentiterateofthePowerMethod,makinguseofknownnonprincipaleigen-valuesoftheWebhyperlinkmatrix.Empirically,weshowthatusingPowerEx-trapolationspeedsupPageRankcomputationby30%onaWebgraphof80
4、mil-lionnodesinrealisticscenariosoverthestandardpowermethod,inawaythatissimpletounderstandandimplement.1IntroductionThePageRankalgorithmfordeterminingthe“importance”ofWebpageshasbecomeacentraltechniqueinWebsearch[9].ThecoreofthePageRankalgorithminvolvescomputi
5、ngtheprincipaleigenvectoroftheMarkovmatrixrepresentingthehyperlinkstructureoftheWeb.AstheWebgraphisverylarge,containingoverabillionnodes,thePageRankvectorisgenerallycomputedoffline,duringthepreprocessingoftheWebcrawl,beforeanyquerieshavebeenissued.Thedevelopmen
6、toftechniquesforcomputingPageRankefficientlyforWeb-scalegraphsisimportantforanumberofreasons.ForWebgraphscontainingabillionnodes,computingaPageRankvectorcantakeseveraldays.ComputingPageRankquicklyisnecessarytoreducethelagtimefromwhenanewcrawliscompletedtowhenth
7、atcrawlcanbemadeavailableforsearching.Furthermore,recentapproachestoperson-alizedandtopic-sensitivePageRankschemes[2,10,6]requirecomputingmanyPage-Rankvectors,eachbiasedtowardscertaintypesofpages.TheseapproachesintensifytheneedforfastermethodsforcomputingPageR
8、ank.ApracticalextrapolationmethodforacceleratingthecomputationofPageRankwasfirstpresentedbyKamvaretal.in[7].Thatworkassumedthatnoneofthenonprinci-paleigenvaluesofthehyperlinkmatrixw
