HITS (z ang. Hypertext Induced Topic Selection albo Hyperlink Induced Topic Search) – algorytm opracowany przez Jona Kleinberga w 1998 z myślą o silniku przeszukującym pod nazwą CLEVER, wykorzystywany do oceny relatywności tekstu względem termu.
Algorytm HITS zakłada, że dokumenty w zbiorze są ze sobą nawzajem połączone, tworząc pewnego rodzaju graf skierowany. W grafie tym węzłami są dokumenty, a krawędziami odnośniki. Krawędzie są skierowane w taki sposób, aby wskazywały na element cytowany, a wychodziły z elementu cytującego. Same założenia modelu wskazują na naturalne wykorzystanie go odnośnie dokumentów hipertekstowych jako zawierających odnośniki (w tym także dokumentów w sieci WWW).
Algorytm HITS ma za podstawę na dwóch ideach: autorytetu (ang. authority) oraz koncentratora (ang. hub). Dokumentem autorytatywnym (autorytetem) jest dokument cytowany wskazywany, taki, na który wskazuje wiele dokumentów (wiele dokumentów cytuje ten dokument). Koncentratorem jest dokument cytujący, który wskazuje na dokumenty autorytarne (dokument cytuje wiele ważnych dokumentów).
Kleinberg opracował oparty na odnośnikach model nadawania autorytetu oraz pokazał jak prowadzi to do metody, która konsekwentnie identyfikuje równocześnie relewantne oraz autorytatywne strony dla zapytania o szerokiej tematyce. Model bazuje na związku, który istnieje pomiędzy autorytetem w danym temacie a tymi stronami, które odsyłają do wielu powiązanych tematycznie autorytetów. Ten drugi typ stron stał się nazwany koncentratorami. Zaobserwowano, że pomiędzy autorytetami oraz koncentratorami istnieje pewna naturalna równowaga w grafie zdefiniowanym przez strukturę odnośników. Wykorzystano to do rozwinięcia algorytmu, który identyfikuje równocześnie oba typy stron. Algorytm operuje na skupionym podgrafie, który stał się skonstruowany z listy wyników wyszukiwania tekstowej wyszukiwarki. Technika konstruowania podgrafu jest zaprojektowana do uzyskania małego zbioru stron, który najprawdopodobniej zawiera najbardziej autorytatywne strony dla danego tematu.
W trakcie obserwacji zauważono, że autorytatywne strony relewantne do początkowego zapytania powinny posiadać nie tylko dużą liczbę odnośników, ale będąc autorytetami we wspólnym temacie, winno istnieć znaczne pokrycie w zbiorze stron, które do nich odsyłają. Dlatego oprócz wyszukania wysoce autorytatywnych stron, spodziewano się znaleźć koncentratory, czyli strony, które posiadają odnośniki do wielu autorytatywnych stron. To właśnie koncentratory trzymają razem autorytety we wspólnym temacie oraz pozwalają pozbyć się niepowiązanych stron z dużą liczbą odnośników.
Koncentratory oraz autorytety wykazują wzajemny, obopólnie wzmacniający związek (ang. mutually reinforcing relationship). Dobry koncentrator to strona, która wskazuje do wielu dobrych autorytetów. Dobry autorytet to strona, która jest wskazywana przez wiele dobrych koncentratorów. Autor zauważył, że rezultaty uzyskane poprzez czystą analizę struktury odsyłaczy dają o wiele lepsze rezultaty, niż wyszukiwarki oparte na przeszukiwaniu tekstu. W tym przypadku zastąpiono globalną analizę całej struktury odsyłaczy w WWW bardziej lokalną metodą analizy małego skupionego podgrafu.
Algorytm skutecznie sprawdza się w szerokim zakresie tematów, gdzie najsilniejsze autorytety świadomie nie zawierają do siebie wzajemnych odnośników. Potrafią one być połączone pośrednio przez warstwę relatywnie anonimowych koncentratorów, które są skorelowane oraz odsyłają do tematycznie powiązanych grup autorytetów. Ten dwupoziomowy wzór powiązań odsłania strukturę pośród obu zbiorów, koncentratorów, które potrafią wzajemnie o sobie nie wiedzieć oraz autorytetów, które potrafią nie chcieć pogodzić się z istnieniem innych autorytetów.
Ostatecznym wynikiem działania algorytmu jest lista węzłów oraz autorytetów z największymi współczynnikami poprawności.
Sprawdź też
Literatura
- J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, pages 668-677, ACM Press, New York, 1998. [1](PDF)
- J. M. Kleinberg. Authoritative sources in a hyperlinked environment. In Journal of the ACM, 46(5), pages 604-632, 1999
- A. Strzelecki. Autorytatywne oraz eksperckie strony źródłem rzetelnych wyników w wyszukiwarkach internetowych, [w:] Informatyka dla przyszłości, pod red. J. Kisielnicki, Wydawnictwo Naukowe Wydziału Zarządzania Uniwersytetu Warszawskiego, Warszawa 2008, s. 193-201 ISBN 978-83-61276-13-5 [2](PDF)