Jon Kleinberg の HITS アルゴリズム

HITS と呼ばれるアルゴリズムをご存知でしょうか。
Jon Kleinberg が考案した、ページの順位付けのためのアルゴリズムです。
Google の PageRank のようなものだと思ってもらってかまいません。

この HITS アルゴリズムが、Yahoo! の検索エンジンに採用されている、
という噂があります。
真偽のほどはわかりませんが、そこかしこでまことしやかに囁かれている割には
あまり日本語の解説記事が無いようなので、
今回はこの HITS アルゴリズムについて説明してみたいと思います。
参考にしたのは Authoritative sources in a hyperlinked environment. という論文です。
論文のドラフトPDFが彼のサイトから入手できます。

背景

まずは HITS アルゴリズムが生まれるための背景について説明します。
この論文が書かれたのは1997年の、まだインターネットが一般には普及していない時代です。
私の記憶を掘り起こしてみても、当時の検索エンジンはお世辞にも精度が良いといえるものではありませんでした。
おそらく、単純にキーワードの出現回数が多いものを上位に表示するようなことをしていたと思います。

当然、この方法では現実的には色々と問題が出てくることになります。
まず第一に、キーワードの出現回数とページの重要度には一般には強い相関関係はありません。
例えば Harvard で検索を行っても、必ずしも Harvard 大学のサイトがトップには表示されません。
Harvard 大学のサイト以外に Harvard という文字列を含むサイトはいくらでも存在しうるからです。
次に、「検索エンジン」というキーワードで検索した場合を考えてください。
このとき、Yahoo は上位に表示されるでしょうか？
Yahoo のページ中に「検索エンジン」という文字列は含まれていないため、残念ながらヒットしません。
このように、ページ内部のテキスト情報だけでそのページを評価するのは限界があります。

ハブとオーソリティ

そこで、Kleinberg はページを評価するのにリンク構造を用いることを考えました。
その際に重要な役割を果たすのが「オーソリティ」「ハブ」という概念です。

オーソリティとは、キーワードに関連するページの中で重要度の高いページのことです。オーソリティとなるページは検索結果の上位に表示されることになります。

ハブとは、多くのオーソリティにリンクを張っている、「物知り」サイトのことです。物知りサイトがリンクを張っているページは重要なページだと推察できるため、このページ自体は検索結果の上位に表示されるかどうかはわかりませんが、オーソリティを発見するために重要な役割を果たしています。

私たちの目的はオーソリティを発見することですが、そのためにはハブを見つける必要があるため、Kleinbergのアルゴリズムでは、このオーソリティとハブを同時に探していきます。

アルゴリズム

それでは具体的なオーソリティの発見方法について説明します。
Google の PageRank の計算方法をご存知の方は、すんなり理解していただけるのではないかと思います。

まず最初に、探索対象となるページを制限します。これは、単純にWWW上の全てのウェブページからオーソリティを探すのは非常に時間がかかるため、余計なページを最初から除去して計算時間を短縮することが目的です。
そのために、既存の検索エンジンなどを使い、与えられたキーワードで検索を行います。そして、そのとき上位に出てきたページを200件ほど、rootページとして取り出します。
この中にオーソリティが含まれていればよいのですが、上で議論したように、一般にここにはオーソリティが含まれているかどうかはわかりません。
したがって、次に、この root ページから/にリンクが張られているページを全てリストアップし、
このページを探索対象とします。

さて、ここからオーソリティを探すのですが、その際の基本的なアイデアは以下のようなものです。

• 良いオーソリティに沢山リンクを張っているハブは、良いハブである
  
• 良いハブから沢山リンクが張られているオーソリティは、良いオーソリティである。
  

Google の PageRank となんとなく似ていますね。
ですので、ここから先の計算方法も似通っています。

その計算方法ですが、まず、全てのページにオーソリティポイント a_i とハブポイント h_i というものを割り当てます。
このポイントが高いものがそれぞれ良いオーソリティあるいはハブとなります。
初期値はいずれも１とし、以下の計算を繰り返し、それぞれのポイントを更新していきます。

1. 各ページ p に対して、そのページがリンクしているページのオーソリティポイントの総和を計算し、p のハブポイント h_p を、その総和で置き換える。
   
2. 各ページ p に対して、そのページへリンクしているページのハブポイントの総和を計算し、p のオーソリティポイント a_p を、その総和で置き換える。
   

例えば、あるページがハブポイント1,3,4 のページからそれぞれリンクされていたとすると、そのページのオーソリティポイントは 1+3+4=8となります。
また同様に、あるページがオーソリティポイント2,4,1 のページにリンクを張っていたとすると、そのページのハブポイントは 2+4+1=7 となります。
このような計算を繰り返していくと、次第に一定の値に収束していきます。

そうして得られたオーソリティポイントの順番で、ページの順位付けが行われます。

最後に

あまりうまい説明になっていないような気がしますが、理解していただけたでしょうか。
大体の雰囲気はつかんでいただけたのではないかと思います。

もちろん、以上は1997年に公表された Kleinberg のアルゴリズムの話であり、
実際に Yahoo! で使用されているアルゴリズムとは全く違うかもしれませんし、
ベースは同じだとしても、色々と修正を加えていることでしょう。
もしこのアルゴリズムが大筋で採用されているのであれば、
Yahoo 対策には Google 対策とは少し異なる方法を用いる必要があることになります。

まぁ、参考程度にしてください。