rank是靜態(tài)的ranking演算法

7.4HITSDate:2008/11/20Speaker:Fan,ChouBinAdvisor:Dr.Koh,JiaLingOutlineIntroductionHITSHITSAlgorithmRelationshipswithCo-CitationandBibliographicCouplingStrengthsandWeaknessesofHITSIntroductionHITSHITSstandsforHypertextInducedTopicSearch.UnlikePageRank

whichisastaticrankingalgorithm,HITSissearchquerydependent.Whentheuserissuesasearchquery,HITSfirstexpandsthelistofrelevantpagesreturnedbyasearchengineandthenproducestworankingsoftheexpandedsetofpages,authorityrankingandhubranking.IntroductionHITSAnauthorityisapagewithmanyin-links.

->ThepagemayhavegoodorauthoritativecontentonsometopicAhubisapagewithmanyout-links.

->Thepageservesasanorganizeroftheinformationonaparticulartopicandpointstomanygoodauthoritypagesonthetopic.IntroductionHITSIntroductionHITSThekeyideaofHITSisthatagoodhubpointstomanygoodauthoritiesandagoodauthorityispointedtobymanygoodhubs.Authoritiesandhubshaveamutualreinforcementrelationship.HITSAlgorithmGivenabroadsearchqueryq,HITScollectsasetofpagesasfollows:

1.Itsendsthequeryqtoasearchenginesystem.Itthencollectsthighestrankedpages.ThissetiscalledtherootsetW.

2.ItthengrowsWbyincludinganypagepointedtobyapageinWandanypagethatpointstoapageinW.ThisgivesalargersetcalledS.,calledthebaseset.

*ThealgorithmrestrictsitssizebyallowingeachpageinWtobringatmostkpagesHITSAlgorithmHITSthenworksonthepagesinSset,assignseverypageinSanauthorityscoreandahubscore.Letthenumberofpagestobestudiedben,useG=(V,E)todenotethe(directed)linkgraphofS.

Visthesetofpages(ornodes)

Eisthesetofdirectededges(orlinks).

Ltodenotetheadjacencymatrixofthegraph.HITSAlgorithmHITSthenworksonthepagesinSset,assignseverypageinSanauthorityscoreandahubscore.Letthenumberofpagestobestudiedben,useG=(V,E)todenotethe(directed)linkgraphofS.

Visthesetofpages(ornodes)

Eisthesetofdirectededges(orlinks).

Ltodenotetheadjacencymatrixofthegraph.HITSAlgorithmLettheauthorityscoreofthepageibea(i),andthehubscoreofpageIbeh(i).Themutualreinforcingrelationshipofthetwoscoresisrepresentedasfollows:HITSAlgorithmWritingtheminthematrixform,weuseatodenotethecolumnvectorwithalltheauthorityscores,andusehtodenotethecolumnvectorwithallthehubscores.

a=(a(1),a(2),…,a(n))T,

h=(h(1),h(2),…,h(n))T.HITSAlgorithmThecomputationofauthorityscoresandhubscoresisbasicallythesameasthecomputationofthePageRankscoresusingthepoweriterationmethod.weuseakandhktodenoteauthorityandhubscoresatthekthiteration,theiterativeprocessesforgeneratingthefinalsolutionsareHITSAlgorithmAftereachiteration,thevaluesarealsonormalized(tokeepthemsmall)sothat..HITSAlgorithmHITSAlgorithmTheiterationendsafterthe1-normsoftheresidualvectorsarelessthansomethresholdsHence,thealgorithmfindstheprincipaleigenvectorsat“equilibrium”asinPageRank.Thepageswithlargeauthorityandhubscoresarebetterauthoritiesandhubsrespectively.HITSwillselectafewtoprankedpagesasauthoritiesandhubs,andreturnthemtotheuser.HITSAlgorithmAlthoughHITSwillalwaysconverge,thereisaproblemwithuniquenessoflimiting(converged)authorityandhubvectors.Itisshownthatforcertaintypesofgraphs,differentinitializationstothepowermethodproducedifferentfinalauthorityandhubvectors.Someresultscanbeinconsistentorwrong.HITSAlgorithmTheHITSalgorithmfindstheprincipaleigenvectors,whichinasenserepresentthemostdenselyconnectedauthoritiesandhubsinthegraphGdefinedbyaquery.However,insomecases,wemayalsobeinterestedinfindingseveraldenselylinkedcollectionsofhubsandauthoritiesamongthesamebasesetofpages.Eachofsuchcollectionscouldpotentially

berelevanttothequerytopic,buttheycouldbewell-separatedfromoneanotherinthegraphG.HITSAlgorithmForexample,

Thequerystringmaybeambiguouswithseveralverydifferentmeanings,e.g.,“jaguar”,whichcouldbeacatoracar.

Thequerystringmayrefertoahighlypolarizedissue,involvinggroupsthatarenotlikelytolinktooneanother,e.g.“abortion”.HITSAlgorithmIneachoftheseexamples,therelevantpagescanbenaturallygroupedintoseveralclusters,alsocalledcommunities.Thesmallerclusters(orcommunities),whicharealsorepresentedbybipartitesubgraphsasthatinFig.7.9,canbefoundbycomputingnon-principaleigenvectors.Non-principaleigenvectorsarecalculatedinasimilarwaytopoweriterationusingmethodssuchasorthogonaliterationandQRiteration.RelationshipswithCo-CitationandBibliographicCouplingAuthoritypagesandhubpageshavetheirmatchesinthebibliometriccitationcontext.Anauthoritypageislikeaninfluentialresearchpaper(publication)whichiscitedbymanysubsequentpapers.Ahubpageislikeasurveypaperwhichcitesmanyotherpapers(includingthoseinfluentialpapers).Thisshowsthattheauthoritymatrix(LTL)ofHITSisinfactthecocitationmatrixCintheWebcontext.RelationshipswithCo-CitationandBibliographicCouplingrecallthatbibliographiccouplingoftwopagesiandj,denotedbyBij,iscomputedaswhichshowsthatthehubmatrix(LLT)ofHITSisthebibliographiccouplingmatrixBintheWebcontext.StrengthsandWeaknessesofHITSThemainstrengthofHITSisitsabilitytorankpagesaccordingtothequerytopic,whichmaybeabletoprovidemorerelevantauthorityandhubpages.Therankingmayalsobecombinedwithinformationretrievalbasedrankings.HITShasseveraldisadvantages:

1.

Itdoesnothavetheanti-spamcapabilityofPageRank.2.AnotherproblemofHITSistopicdrift.

3.Thequerytimeevaluationisalsoamajordrawback.StrengthsandWeaknessesofHITSOvertheyears,manyresearcherstriedtodealwiththeseproblems….LempelandMoranproposedSALSA,astochasticalgorithmforlinkstructureanalysis.SALSAcombinessomefeaturesofbothPageRankandHITStoimprovetheauthorityandhubcomputation.ItcaststheproblemastwoMarkovchainsStrengthsandWeaknessesofHITSBharatandHenzingerproposedasimple