HITSアルゴリズム

ハイパーリンク誘導トピック検索( HITS 、ハブとオーソリティとも呼ばれる) は、ジョン・クラインバーグが開発した、Web ページを評価するリンク分析 アルゴリズムです。ハブとオーソリティの背後にあるアイデアは、インターネットが最初に形成されたときの Web ページの作成に関する特定の洞察から生まれました。つまり、ハブと呼ばれる特定の Web ページは、保持する情報に関して実際には権威があるわけではないが、ユーザーを他の権威のあるページに直接導く広範な情報カタログの編集物として使用された大規模なディレクトリとして機能していました。言い換えると、優れたハブは他の多くのページを指し示すページを表し、優れたオーソリティは多くの異なるハブによってリンクされているページを表します。^[1]

したがって、このスキームでは、各ページに 2 つのスコアを割り当てます。ページのコンテンツの価値を推定する権威と、他のページへのリンクの価値を推定するハブ値です。

科学雑誌の重要性をランク付けするために、多くの方法が使われてきました。その 1 つがガーフィールドのインパクト ファクターです。ScienceやNatureなどの雑誌は多数の引用で満たされているため、これらの雑誌のインパクト ファクターは非常に高くなります。したがって、引用数がほぼ同じで、これらの雑誌の 1 つがScienceやNatureから多くの引用を受けている 2 つのあまり知られていない雑誌を比較する場合、この雑誌はより高いランクにランク付けされる必要があります。言い換えれば、重要な雑誌から引用を受ける方が、重要でない雑誌から引用を受けるよりも良いということです。^[2]

この現象はインターネットでも発生します。ページへのリンク数を数えると、Web 上でのそのページの知名度を大まかに見積もることができますが、リンクがほとんどないページでも、そのうち 2 つが Yahoo !、Google、MSNなどのサイトのホームページから来ている場合は、知名度が高い場合があります。これらのサイトは非常に重要であり、検索エンジンでもあるため、ページは実際の関連性よりもはるかに高いランクにランクされることがあります。

HITS アルゴリズムでは、最初のステップは、検索クエリに最も関連性の高いページを取得することです。このセットはルート セットと呼ばれ、テキストベースの検索アルゴリズムによって返される上位のページを取得することで取得できます。ルート セットからリンクされているすべての Web ページと、ルート セットにリンクしている一部のページをルート セットに追加することで、ベース セットが生成されます。ベース セット内の Web ページとそれらのページ間のすべてのハイパーリンクは、フォーカスされたサブグラフを形成します。HITS の計算は、このフォーカスされたサブグラフに対してのみ実行されます。Kleinberg によると、ベース セットを構築する理由は、最も強力なオーソリティのほとんど (または多く) が含まれるようにするためです。

権威値とハブ値は、相互再帰で相互に定義されます。権威値は、そのページを指すスケールされたハブ値の合計として計算されます。ハブ値は、それが指すページのスケールされた権威値の合計です。実装によっては、リンクされたページの関連性も考慮されます。

アルゴリズムは一連の反復を実行し、各反復は次の 2 つの基本ステップで構成されます。

• 権威の更新: 各ノードの権威スコアを、そのノードを指す各ノードのハブ スコアの合計と等しくなるように更新します。つまり、情報のハブとして認識されているページからリンクされているノードには、高い権威スコアが与えられます。
• ハブ更新: 各ノードのハブ スコアを、それが指す各ノードの権威スコアの合計と等しくなるように更新します。つまり、ノードは、主題の権威であると見なされるノードにリンクすることで、高いハブ スコアが与えられます。

ノードのハブ スコアと権限スコアは、次のアルゴリズムで計算されます。

• 各ノードのハブ スコアと権限スコアが 1 である状態から開始します。
• 権限更新ルールを実行する
• ハブ更新ルールを実行する
• 各 Hub スコアをすべての Hub スコアの二乗の合計の平方根で割り、各 Authority スコアをすべての Authority スコアの二乗の合計の平方根で割って、値を正規化します。
• 必要に応じて2番目の手順から繰り返します。

HITS は、PageとBrinのPageRankと同様に、 Web 上のドキュメントのリンクに基づく反復アルゴリズムです。ただし、いくつかの大きな違いがあります。

• これは、PageRank の場合のようにすべてのドキュメントのセットではなく、「関連」ドキュメントの小さなサブセット (「フォーカスされたサブグラフ」または基本セット) に対して処理されます。
• これはクエリに依存します。異なるクエリに対して表示される異なるベースセットが指定されると、同じページでも異なるハブ/権限スコアが付与されることがあります。
• 当然のことながら、インデックス作成時ではなくクエリ時に実行する必要があり、クエリ時の処理に伴うパフォーマンスの低下を伴います。
• 単一のスコアではなく、ドキュメントごとに 2 つのスコア (ハブと権限) を計算します。
• これは検索エンジンでは一般的に使用されていません (ただし、 Ask Jeeves/Ask.comに買収されたTeomaでは同様のアルゴリズムが使用されていたと言われています)。

ランキングを開始するには、各ページ ととします。 2 種類の更新を検討します: 権威更新ルールとハブ更新ルールです。 各ノードのハブ/権威スコアを計算するために、権威更新ルールとハブ更新ルールを繰り返し適用します。 ハブ権威アルゴリズムの k ステップ アプリケーションでは、最初に権威更新ルールを k 回適用し、次にハブ更新ルールを適用します。 ${\displaystyle \mathrm {認証} (p)=1}$${\displaystyle \mathrm {ハブ} (p)=1}$${\displaystyle p}$

各 について、をに更新します。ここで、はページ にリンクしているすべてのページです。つまり、ページのオーソリティ スコアは、そのページを指しているすべてのページのハブ スコアの合計です。 ${\displaystyle p}$${\displaystyle \mathrm {認証} (p)}$${\displaystyle \mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)}$${\displaystyle P_{\mathrm {to} }}$${\displaystyle p}$

各 について、に更新します。ここで は、ページがリンクしているすべてのページです。つまり、ページのハブ スコアは、そのページが指しているすべてのページのオーソリティ スコアの合計です。 ${\displaystyle p}$${\displaystyle \mathrm {ハブ} (p)}$${\displaystyle \mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)}$${\displaystyle P_{\mathrm {from} }}$${\displaystyle p}$

ノードの最終的なハブ権限スコアは、アルゴリズムを無限に繰り返した後に決定されます。ハブ更新ルールと権限更新ルールを直接繰り返し適用すると、値が発散するため、各反復の後にマトリックスを正規化する必要があります。したがって、このプロセスから取得される値は最終的に収束します。

G := G内の各ページpの ページセット
do p .auth = 1 // p .auth はページpのオーソリティスコアp .hub = 1 // p .hub は1からkまでのステップにおけるページpのハブスコアdo // k ステップにわたってアルゴリズムを実行する 
    
    

    ノルム = 0
    G内の各ページpに対して、  まずすべての権限値を更新します。p
         .auth = 0。p.incomingNeighbors
        内の各ページqに対して、次の操作を実行します。// p.incomingNeighborsはpにリンクするページのセットです。p .auth += q .hub  
            
        norm += square( p .auth) // 正規化するために二乗された認証値の合計を計算する
    ノルム = sqrt(ノルム)
    Gの各ページpに対して、次の操作を実行します  // 認証スコアを更新します 
        p .auth = p .auth / norm // 認証値を正規化します 
    ノルム = 0
    G内の各ページpに対して、次の操作を実行します  // 次に、すべてのハブ値を更新します
        p .hub = 0
         p.outgoingNeighbors内の各ページrに対して、次の操作を実行します// p.outgoingNeighborsは、 p がリンクする
            ページのセットですp .hub += r .auth  
        norm += square( p .hub) // 正規化するためにハブ値の二乗の合計を計算する
    ノルム = sqrt(ノルム)
    Gの各ページpに対して、次の操作を実行します  // 次に、すべてのハブ値を更新します
        p .hub = p .hub / norm // ハブ値を正規化します
 

上記の疑似コードでは、ハブと権限の値が収束します。

以下のコードは収束しません。アルゴリズムが実行されるステップ数を制限する必要があるためです。ただし、これを回避する 1 つの方法は、各「ステップ」の後にハブと権限の値を正規化することです。つまり、各権限の値をすべての権限の値を 2 乗した合計の平方根で割り、各ハブの値をすべてのハブの値を 2 乗した合計の平方根で割ります。これは、上記の疑似コードで実行していることです。

G := G内の各ページpの ページセット
do p .auth = 1 // p .auth はページpのオーソリティスコアp .hub = 1 // p .hub はページpのハブスコア 
    
    

function HubsAndAuthorities( G )
     for step from 1 to k do // k ステップのアルゴリズムを実行します。
         for each page p in G  do   // 最初にすべての権限値を更新します。
             p .auth = 0
             for each page q in p.incomingNeighbors  do // p.incomingNeighbors はp
                にリンクするページのセットです。p .auth += q .hub
         for each page p in G  do   // 次にすべてのハブ値を更新します。
             p .hub = 0
             for each page r in p.outgoingNeighbors  do // p.outgoingNeighbors はpにリンクする
                ページのセットです。 p .hub += r .auth

• ページランク

• Kleinberg, Jon (1999). 「ハイパーリンク環境における信頼できる情報源」(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) 「Web ドキュメントにおける HITS ベースのアルゴリズムの改善」第 11 回国際ワールド ワイド ウェブ会議 (WWW 2002) の議事録。ホノルル、ハワイ。ISBN 978-1-880672-20-4. 2005年4月3日時点のオリジナルよりアーカイブ。2005年6月3日閲覧。{{cite book}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)

• 米国特許6,112,202
• リレーショナルデータベースからデータ検索エンジンを作成する HITS に基づく C# の検索エンジン