HITS-algoritm

Hyperlink-Induced Topic Search ( HITS ; även känd som nav och myndigheter ) är en länkanalysalgoritm som betygsätter webbsidor, utvecklad av Jon Kleinberg . Idén bakom Hubs and Authorities härrörde från en speciell insikt i skapandet av webbsidor när Internet ursprungligen bildades; det vill säga, vissa webbsidor, så kallade hubbar, fungerade som stora kataloger som faktiskt inte var auktoritativa i den information de innehöll, utan användes som sammanställningar av en bred katalog av information som ledde användare direkt till andra auktoritativa sidor. Med andra ord representerar ett bra nav en sida som pekade på många andra sidor, medan en bra auktoritet representerar en sida som är länkad av många olika nav.

Schemat tilldelar därför två poäng för varje sida: dess auktoritet, som uppskattar värdet av sidans innehåll, och dess navvärde, som uppskattar värdet av dess länkar till andra sidor.

Historia

I tidskrifter

Många metoder har använts för att rangordna vikten av vetenskapliga tidskrifter. En sådan metod är Garfields impact factor . Tidskrifter som Science och Nature är fyllda med många citat, vilket gör att dessa tidskrifter har mycket höga påverkansfaktorer. Så när man jämför två mer obskyra tidskrifter som har fått ungefär lika många citeringar men en av dessa tidskrifter har fått många citeringar från Science och Nature , behöver denna tidskrift rankas högre. Det är med andra ord bättre att få citat från en viktig tidskrift än från en oviktig.

På webben

Detta fenomen förekommer även på Internet . Att räkna antalet länkar till en sida kan ge oss en allmän uppskattning av dess framträdande plats på webben, men en sida med väldigt få inkommande länkar kan också vara framträdande om två av dessa länkar kommer från hemsidorna på webbplatser som Yahoo! , Google eller MSN . Eftersom dessa webbplatser är av mycket stor betydelse men också är sökmotorer , kan en sida rankas mycket högre än dess faktiska relevans.

Algoritm

Expandera rotuppsättningen till en basuppsättning

I HITS-algoritmen är det första steget att hämta de mest relevanta sidorna till sökfrågan. Denna uppsättning kallas rotuppsättningen och kan erhållas genom att ta de översta sidorna som returneras av en textbaserad sökalgoritm. En basuppsättning genereras genom att utöka rotuppsättningen med alla webbsidor som är länkade från den och några av sidorna som länkar till den. Webbsidorna i basuppsättningen och alla hyperlänkar mellan dessa sidor bildar en fokuserad subgraf. HITS-beräkningen utförs endast på denna fokuserade subgraf . Enligt Kleinberg är anledningen till att konstruera en basuppsättning för att säkerställa att de flesta (eller många) av de starkaste myndigheterna ingår.

Auktoritets- och navvärden definieras i termer av varandra i en ömsesidig rekursion . Ett auktoritetsvärde beräknas som summan av de skalade navvärdena som pekar på den sidan. Ett navvärde är summan av de skalade auktoritetsvärdena för sidorna det pekar på. Vissa implementeringar tar också hänsyn till de länkade sidornas relevans.

Algoritmen utför en serie iterationer, som var och en består av två grundläggande steg:

• Auktoritetsuppdatering : Uppdatera varje nods auktoritetspoäng så att den är lika med summan av navpoängen för varje nod som pekar på den. Det vill säga att en nod ges ett högt auktoritetspoäng genom att länkas från sidor som känns igen som Hubs för information.
• Hubuppdatering : Uppdatera varje nods navpoäng så att den är lika med summan av auktoritetspoängen för varje nod som den pekar på. Det vill säga att en nod ges ett högt navpoäng genom att länka till noder som anses vara auktoriteter i ämnet.

Hubpoängen och auktoritetspoängen för en nod beräknas med följande algoritm:

• Börja med att varje nod har ett navpoäng och auktoritetspoäng på 1.
• Kör regeln för auktoritetsuppdatering
• Kör navuppdateringsregeln
• Normalisera värdena genom att dividera varje navpoäng med kvadratroten av summan av kvadraterna av alla navpoäng, och dividera varje auktoritetspoäng med kvadratroten av summan av kvadraterna av alla auktoritetspoäng.
• Upprepa från det andra steget vid behov.

HITS, som Page och Brins PageRank , är en iterativ algoritm baserad på länkningen av dokumenten på webben . Det har dock några stora skillnader:

• Det är frågeberoende, det vill säga att poängen (nav och myndighet) som resulterar från länkanalysen påverkas av söktermerna;
• Som en följd av detta exekveras det vid frågetid, inte vid indexering, med den associerade träffen på prestanda som åtföljer frågetidsbehandling.
• Det används inte ofta av sökmotorer. (Även om en liknande algoritm sades användas av Teoma , som förvärvades av Ask Jeeves/Ask.com .)
• Den beräknar två poäng per dokument, nav och auktoritet, i motsats till en enda poäng;
• Den behandlas på en liten delmängd av "relevanta" dokument (en "fokuserad subgraf" eller basuppsättning), inte alla dokument som var fallet med PageRank.

I detalj

För att börja rangordningen låter vi $\mathrm {auth} (p)=1$ och $\mathrm {hub} (p) =1$ för varje sida $p$ . Vi överväger två typer av uppdateringar: Authority Update Rule och Hub Update Rule. För att beräkna hubb-/auktoritetspoängen för varje nod tillämpas upprepade iterationer av behörighetsuppdateringsregeln och navuppdateringsregeln. En k-stegsapplikation av Hub-Authority-algoritmen innebär att man ansöker om k gånger först Authority Update Rule och sedan Hub Update Rule.

Behörighetsuppdateringsregel

För varje $p$ uppdaterar vi $\mathrm {auth} (p)$ till ${\displaystyle \mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)} där P t$ o $P_ {\mathrm {to} }}$ är alla sidor som länkar till sidan $p$ . Det vill säga, en sidas auktoritetspoäng är summan av alla navpoäng på sidor som pekar på den.

Hubuppdateringsregel

För varje $p$ uppdaterar vi $\mathrm {hub} (p)$ till $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ där ${ \displaystyle P_{\mathrm {från} }}$ är alla sidor som sidan $p$ länkar till. Det vill säga, en sidas navpoäng är summan av alla auktoritetspoäng på sidor den pekar på.

Normalisering

De slutliga nav-auktoritetspoängen för noder bestäms efter oändliga upprepningar av algoritmen. Eftersom direkt och iterativ tillämpning av navuppdateringsregeln och auktoritetsuppdateringsregeln leder till divergerande värden, är det nödvändigt att normalisera matrisen efter varje iteration. Således kommer värdena som erhålls från denna process så småningom att konvergera.

Pseudokod

 
    
    
  
                 G  := uppsättning sidor  för varje  sida  p  i  G  do  p  .auth = 1 //  p  .auth är sidans auktoritetspoäng  p  p  .hub = 1 //  p  .hub är navpoängen för sidan  p  för  steg  från  1  till  k  do  // kör algoritmen för k steg norm = 0  för varje  sida  p  i  G  do  // uppdatera alla auktoritetsvärden först  p  .auth = 0  för varje  sida  q  i  p.incomingNeighbors  do  //  p.incomingNeighbors  är uppsättningen sidor som länkar till  p  p  .auth +=  q  .hub norm += square(  p  .auth) // beräkna summan av de kvadrerade auth-värdena för att normalisera norm = sqrt(norm)  för varje  sida  p  i  G  gör  // uppdatera auth-poängen  p  .auth =  p  .auth / norm // normalisera auth-värdena norm = 0  för varje  sida  p  i  G  gör  // uppdatera sedan alla navvärden  p  .hub = 0  för varje  sida  r  i  p .outgoingNeighbors  do  //  p.outgoingNeighbors  är uppsättningen sidor som  p  länkar till  p  .hub +=  r  .auth norm += square(  p  .hub) // beräkna summan av de kvadratiska navvärdena för att normalisera norm = sqrt( norm)  för varje  sida  p  i  G  gör  // uppdatera sedan alla navvärden  p  .hub =  p  .hub / norm // normalisera navvärdena 

Nav- och auktoritetsvärdena konvergerar i pseudokoden ovan.

Koden nedan konvergerar inte, eftersom det är nödvändigt att begränsa antalet steg som algoritmen körs för. Ett sätt att komma runt detta skulle dock vara att normalisera nav- och auktoritetsvärdena efter varje "steg" genom att dividera varje auktoritetsvärde med kvadratroten av summan av kvadraterna av alla auktoritetsvärden, och dividera varje navvärde med kvadratroten av summan av kvadraterna av alla navvärden. Detta är vad pseudokoden ovan gör.

Icke-konvergerande pseudokod

 
    
    

  
                   G  := uppsättning sidor  för varje  sida  p  i  G  do  p  .auth = 1 //  p  .auth är sidans auktoritetspoäng  p  p  .hub = 1 //  p  .hub är navpoängen för sidan  p  -funktionen  HubsAndAuthorities(  G  )  för  steg  från  1  till  k  do  // kör algoritmen för k steg  för varje  sida  p  i  G  do  // uppdatera alla auktoritetsvärden först  p  .auth = 0  för varje  sida  q  i  p.incomingNeighbors  do  //  p .incomingNeighbors  är uppsättningen sidor som länkar till  p  p  .auth +=  q  .hub  för varje  sida  p  i  G  do  // uppdaterar sedan alla navvärden  p  .hub = 0  för varje  sida  r  i  p.outgoingNeighbors  do  //  p .outgoingNeighbors  är uppsättningen sidor som  p  länkar till  p  .hub +=  r  .auth 

Se även

• PageRank

•    Kleinberg, Jon (1999). "Auktoritativa källor i en hyperlänkad miljö" (PDF) . Journal of the ACM . 46 (5): 604–632. CiteSeerX 10.1.1.54.8485 . doi : 10.1145/324133.324140 . S2CID 221584113 .
•   Li, L.; Shang, Y.; Zhang, W. (2002). "Förbättring av HITS-baserade algoritmer på webbdokument" . Proceedings of the 11th International World Wide Web Conference (WWW 2002) . Honolulu, HI. ISBN 978-1-880672-20-4 .

externa länkar

• US-patent 6,112,202
• Skapa en datasökmotor från en relationsdatabas Sökmotor i C# baserat på HITS