HITSアルゴリズム

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

そのため、この制度では各ページに2つのスコアを割り当てます。1つはページのコンテンツの価値を評価する「オーソリティ」、もう1つは他のページへのリンクの価値を評価する「ハブ値」です。

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

G := ページのセット 各ページpについて、p.auth = 1 // p.authはページpのオーソリティ スコアですp.hub = 1 // p.hubはページpのハブ スコアですステップ1からkまで、k ステップにわたってアルゴリズムを実行します ノルム = 0 Gの各ページpに対して、 // まずすべてのオーソリティ値を更新します。 p.auth = 0 p.incomingNeighborsの各ページqに対して、 // p.incomingNeighbors はpにリンクしているページのセットです。p.auth += q.hub norm += square( p .auth) // 認証値の二乗の合計を計算して正規化する norm = sqrt(norm) 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) // 正規化するために、ハブ値の二乗の合計を計算します norm = sqrt(norm) Gの各ページpに対して、 // すべてのハブ値を更新します。 p.hub = p.hub / norm // ハブ値を正規化します

上記の擬似コードでは、ハブ値とオーソリティ値が収束する。

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

G := ページのセット 各ページp in Gに対して、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-42005年4月3日にオリジナルからアーカイブされました。 2005年6月3日に取得。{{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

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