HITSalgoritmen

HITS-algoritmen, eller Hyperlink-Induced Topic Search, är en länkbaserad rankingalgoritm som introducerades av Jon Kleinberg 1998 för att rangordna webbsidor inom ett givet ämnesområde. Algoritmen verkar på en riktad graf där noderna representerar webbsidor och kanter representerar hyperlänkar mellan sidorna. För ett givet sökpaket används ofta en delgraf av sidor relevanta för frågan, och HITS används för att rangordna sidorna inom denna delgraf.

Algoritmen delar sidor i två typer: hub-sidor, som länkar till många andra sidor, och authorities, som får länkar från många hub-sidor. Hub-sidornas poäng speglar hur väl de pekar till relevanta authorities, medan auktoritetspoängens uppgift är att sammanfatta hur många och hur starkt länkade sidorna är av hubbarna.

Algoritmen beräknas iterativt. En vanlig uppsättning uppdateringar är: a_i^t = sum_{j: j länkar till i} h_j^{t-1}, där auktoritetspoängen uppdateras som summan av hubbpoängen hos sidor som länkar till den; och h_i^t = sum_{j: i länkar till j} a_j^{t-1}, där hubbpoängen uppdateras som summan av auktoritetspoängen hos sidorna som hinnas till. Efter varje iteration normaliseras vektorerna för att undvika explosion. I praktiken konvergerar dessa vektorer till störst egenvektor av matriserna A^T A och A A^T, där A är anpassningsmatrisen för länkarna.

Användningen är fokuserad och parameterstyrd: HITS bygger en ämnesspecifik bild av ett delnätverk och används ofta som ett steg i en större sökprocess när frågan styr vilka sidor som inkluderas i analysen. Begränsningar inkluderar beräkningskostnader på stora grafstrukturer, känslighet för manipulering av länkar och beroende av en väl avgränsad delgraf. Variants på området inkluderar Topic-Specific HITS (STHITS) som försöker förbättra ämnesspecifikhet och robusthet. Jämfört med PageRank ger HITS två separata poäng (hub och authority) och är mer fokuserad på relationer inom en given delgraf, medan PageRank är global och mer skevar mot sidor med stort många links.