Algorytm HITS

Hyperlink-Induced Topic Search ( HITS ; znane również jako huby i autorytety ) to algorytm analizy linków , który ocenia strony internetowe, opracowany przez Jona Kleinberga . Idea Hubów i Władz wynikała ze szczególnego wglądu w tworzenie stron internetowych, gdy pierwotnie tworzył się Internet; to znaczy, niektóre strony internetowe, zwane hubami, służyły jako duże katalogi, które w rzeczywistości nie były autorytatywne pod względem przechowywanych informacji, ale były używane jako kompilacje szerokiego katalogu informacji, które prowadziły użytkowników bezpośrednio do innych autorytatywnych stron. Innymi słowy, dobry hub reprezentuje stronę, która wskazywała na wiele innych stron, podczas gdy dobry autorytet reprezentuje stronę, do której prowadzi wiele różnych hubów.

W związku z tym schemat przypisuje każdej stronie dwie oceny: autorytet, który szacuje wartość zawartości strony, oraz wartość centrum, która szacuje wartość linków do innych stron.

Historia

W czasopismach

Do uszeregowania znaczenia czasopism naukowych zastosowano wiele metod. Jedną z takich metod jest współczynnik wpływu Garfielda . Czasopisma takie jak „Science” czy „ Nature” wypełnione są licznymi cytowaniami, co sprawia, że ​​czasopisma te mają bardzo wysokie współczynniki oddziaływania. Tak więc, porównując dwa mniej znane czasopisma, które otrzymały mniej więcej taką samą liczbę cytowań, ale jedno z tych czasopism otrzymało wiele cytowań z Science i Nature , to czasopismo powinno znaleźć się wyżej w rankingu. Innymi słowy, lepiej jest otrzymywać cytaty z ważnego czasopisma niż z nieistotnego.

W Internecie

Zjawisko to występuje również w Internecie . Liczenie linków do strony może dać nam ogólne oszacowanie jej widoczności w sieci, ale strona z bardzo małą liczbą linków przychodzących może również być widoczna, jeśli dwa z tych linków pochodzą ze stron głównych witryn takich jak Yahoo! , Google lub MSN . Ponieważ witryny te mają bardzo duże znaczenie, ale są również wyszukiwarkami , strona może znaleźć się w rankingu znacznie wyżej niż jej rzeczywista trafność.

Algorytm

Rozszerzanie zestawu głównego do zestawu podstawowego

W algorytmie HITS pierwszym krokiem jest pobranie najbardziej odpowiednich stron dla zapytania wyszukiwania. Ten zestaw nazywany jest zbiorem głównym i można go uzyskać, biorąc górne strony zwrócone przez algorytm wyszukiwania tekstowego. Zestaw podstawowy jest generowany przez rozszerzenie zestawu głównego o wszystkie strony internetowe, do których prowadzą z niego łącza, oraz niektóre strony, które prowadzą do niego. Strony internetowe w zestawie podstawowym i wszystkie hiperłącza między tymi stronami tworzą zogniskowany podwykres. Obliczenia HITS są wykonywane tylko na tym skupionym podgrafie . Według Kleinberga powodem konstruowania zestawu podstawowego jest zapewnienie uwzględnienia większości (lub wielu) najsilniejszych autorytetów.

Wartości autorytetu i koncentratora są definiowane względem siebie we wzajemnej rekurencji . Wartość uprawnień jest obliczana jako suma przeskalowanych wartości centrum wskazujących tę stronę. Wartość centrum to suma przeskalowanych wartości uprawnień stron, na które wskazuje. Niektóre implementacje uwzględniają również znaczenie stron, do których prowadzą łącza.

Algorytm wykonuje serię iteracji, z których każda składa się z dwóch podstawowych kroków:

• Aktualizacja uprawnień : Zaktualizuj ocenę uprawnień każdego węzła , aby była równa sumie ocen centrum każdego węzła, który na nią wskazuje. Oznacza to, że węzeł otrzymuje wysoką ocenę autorytetu poprzez połączenie ze stron, które są rozpoznawane jako Centra informacyjne.
• Aktualizacja centrum : zaktualizuj ocenę centrum każdego węzła, aby była równa sumie ocen autorytetu każdego węzła, na który wskazuje. Oznacza to, że węzeł otrzymuje wysoki wynik koncentratora, łącząc się z węzłami, które są uważane za autorytety w tej dziedzinie.

Ocena centrum i ocena autorytetu dla węzła jest obliczana za pomocą następującego algorytmu:

• Zacznij od tego, aby każdy węzeł miał ocenę centrum i ocenę autorytetu równą 1.
• Uruchom regułę aktualizacji uprawnień
• Uruchom regułę aktualizacji centrum
• Normalizuj wartości, dzieląc wynik każdego Centrum przez pierwiastek kwadratowy z sumy kwadratów wszystkich wyników Centrum i dzieląc każdy wynik Autorytetu przez pierwiastek kwadratowy z sumy kwadratów wszystkich wyników Autorytetu.
• W razie potrzeby powtórz od kroku drugiego.

HITS, podobnie jak PageRank PageRank i Brin , to iteracyjny algorytm oparty na powiązaniu dokumentów w sieci . Ma jednak kilka istotnych różnic:

• Zależy od zapytania, to znaczy na wyniki (centra i autorytet) wynikające z analizy linków mają wpływ wyszukiwane hasła;
• W związku z tym jest wykonywany w czasie zapytania, a nie w czasie indeksowania, z powiązanym uderzeniem w wydajność, które towarzyszy przetwarzaniu w czasie zapytania.
• Nie jest powszechnie używany przez wyszukiwarki. (Chociaż podobno podobny algorytm był używany przez Teoma , który został przejęty przez Ask Jeeves/Ask.com ).
• Oblicza dwa wyniki na dokument, centrum i autorytet, w przeciwieństwie do jednego wyniku;
• Jest przetwarzany na niewielkim podzbiorze „istotnych” dokumentów („zogniskowany podwykres” lub zestaw podstawowy), a nie na wszystkich dokumentach, jak miało to miejsce w przypadku PageRank.

Szczegółowo

Aby rozpocząć ranking, niech za $\ Displaystyle \ operatorname {auth} (p) = 1}$ i ${\ Displaystyle \ operatorname {hub} (p) = 1}$ dla każdej strony ${\ displaystyle p}$ . Rozważamy dwa rodzaje aktualizacji: Reguła aktualizacji urzędu i Reguła aktualizacji centrum. Aby obliczyć punktację centrum/autorytetu dla każdego węzła, stosowane są powtarzane iteracje Reguły aktualizacji urzędu i Reguły aktualizacji centrum. K-etapowe zastosowanie algorytmu Hub-Authority pociąga za sobą zastosowanie k razy najpierw Reguły Aktualizacji Autorytetu, a następnie Reguły Aktualizacji Huba.

Reguła aktualizacji uprawnień

Dla każdego aktualizujemy $( q )$$p$$_$ za gdzie ${\ displaystyle P _ {\ operatorname {to}}}$ to wszystkie strony, które prowadzą do strony ${\ displaystyle p}$ . Oznacza to, że ocena autorytetu strony jest sumą wszystkich ocen w centrum stron, które na nią wskazują.

Reguła aktualizacji centrum

$_$ każdego aktualizujemy do $godz$$)$ gdzie $operatorname {z}}}$$\$ to wszystkie strony, do których prowadzi link. Oznacza to, że ocena centrum strony jest sumą wszystkich ocen autorytetu stron, na które wskazuje.

Normalizacja

Ostateczne oceny hub-authority węzłów są określane po nieskończonych powtórzeniach algorytmu. Ponieważ bezpośrednie i iteracyjne stosowanie Reguły aktualizacji koncentratora i Reguły aktualizacji uprawnień prowadzi do rozbieżnych wartości, konieczne jest znormalizowanie macierzy po każdej iteracji. W ten sposób wartości uzyskane z tego procesu ostatecznie będą zbieżne.

Pseudo kod

 
    
    
  G  := zestaw stron  dla każdej  strony  p  w  G  do  p  .auth = 1 //  p  .auth to ocena autorytetu strony  p  p  .hub = 1 //  p  .hub to ocena centrum strony  p  dla  krok  od  1  do  k  wykonaj  // uruchom algorytm dla k kroków norm = 0  dla każdej  strony  p  w  G  wykonaj  // najpierw zaktualizuj wszystkie wartości uprawnień  p  
              .auth = 0  dla każdej  strony  q  w  p.incomingNeighbors  do  //  p.incomingNeighbors  to zbiór stron prowadzących do  p  p  .auth +=  q  .hub norm += square(  p  .auth) // oblicz sumę podniesione do kwadratu wartości autoryzacji w celu znormalizowania norm = sqrt(norm)  dla każdej  strony  p  w  G  do  // zaktualizuj wyniki autoryzacji  p  .auth =  p    .auth / norm // znormalizuj wartości autoryzacji norm = 0  dla każdej  strony  p  w  G  do  // następnie zaktualizuj wszystkie wartości centrum  p  .hub = 0  dla każdej  strony  r  w  p.outgoingNeighbors  do  //  p.outgoingNeighbors  jest zbiorem strony, które  p  prowadzą do  p  .hub +=  r  .auth norm += square(  p   .hub) // oblicz sumę kwadratów wartości hubów, aby znormalizować norm = sqrt(norm)  dla każdej  strony  p  w  G  do  // następnie zaktualizuj wszystkie wartości hubów  p  .hub =  p  .hub / norm // znormalizuj wartości hubów 

Wartości koncentratora i uprawnień są zbieżne w powyższym pseudokodzie.

Poniższy kod nie jest zbieżny, ponieważ konieczne jest ograniczenie liczby kroków wykonywanych przez algorytm. Jednym ze sposobów obejścia tego problemu byłoby jednak znormalizowanie wartości koncentratora i autorytetu po każdym „kroku” poprzez podzielenie każdej wartości autorytetu przez pierwiastek kwadratowy z sumy kwadratów wszystkich wartości autorytetu i podzielenie każdej wartości koncentratora przez pierwiastek kwadratowy z sumy kwadratów wszystkich wartości piast. To właśnie robi powyższy pseudokod.

Niezbieżny pseudokod

 
    
    

  G  := zestaw stron  dla każdej  strony  p  w  G  do  p  .auth = 1 //  p  .auth to ocena autorytetu strony  p  p  .hub = 1 //  p  .hub to ocena centrum  funkcji  p strony   HubsAndAuthorities(  G  )  dla  kroku  od  1  do  k  do  // uruchom algorytm dla k kroków  dla każdej  strony  p  w  G  do  
                  // najpierw zaktualizuj wszystkie wartości uprawnień  p  .auth = 0  dla każdej  strony  q  w  p.incomingNeighbors  do  //  p.incomingNeighbors  to zestaw stron prowadzących do  p  p  .auth +=  q  .hub  dla każdej  strony  p  w  G  do  // następnie zaktualizuj wszystkie wartości centrum  p  .hub = 0  dla każdej  strony  r  w  p.outgoingNeighbors   do  //  p.outgoingNeighbors  to zestaw stron, do których  p  łączy  p  .hub +=  r  .auth 

Zobacz też

• PageRank

•    Kleinberg, Jon (1999). „Autorytatywne źródła w środowisku z hiperłączami” (PDF) . Dziennik 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). „Poprawa algorytmów opartych na HITS w dokumentach internetowych” . Materiały z 11. Międzynarodowej Konferencji World Wide Web (WWW 2002) . Honolulu, Hawaje. ISBN 978-1-880672-20-4 .

Linki zewnętrzne

• Patent US 6,112,202
• Tworzenie wyszukiwarki danych z relacyjnej bazy danych Wyszukiwarka w C# oparta na HITS