HITS とはハイパーリンク構造（リンクや被リンクなど）を用いてウェブページのスコアを計算する方法。Google で用いられている PageRank の仲間。

HITS は Authority score(以下、auth) と Hub score(以下、hub) の2種類のスコアを算出する。

アルゴリズム概要

各ページiの持つ auth を 、hub を とする。 をウェブグラフ全てのリンクの集合とし、 はページiからjへのリンクを表す(有無：1 or 0)とする。そして、以下の式（オリジナル論文での式）を繰り返し計算し最終的な auth と hub を得る。初期値は何らかの方法で与えられるとする。



実例で解説。下図のようなウェブグラフがあるとする。



初期値 は全て1として2回繰り返して計算してみる。

	0	1	2	3	4	5
	1	1	1	1	1	1
	1	0	2	1	3	0
	5	1	3	0	3	3
	1	0	8	3	11	0
	19	1	11	0	11	11

表の見方： は2番のノードのAuthorityスコアで、0番(=1)と4番(=1)からリンクが張られているので 1+1=2 となる。また、 は0番のノードのHubスコアでには2番(=2)と4番(=3)へリンクが張られているので 2+3=5 となる。

k=2 の時点では一番 Authority score が高いのが 4 番のページ(11)で、一番 Hub score が高いのが 0 番のページ(19)となる。

行列による計算

実装に際しては行列として扱うと楽。リンクは隣接行列で表すことができる。

前述のウェブグラフの隣接行列は下記のようになる。



で、最初にあげたオリジナルの式は下記の形に置き換えらえる（はの転置行列）。



そしていろいろあって下記の形に置き換えらえる（って、代入するだけ）。



つまり auth の計算は行列とベクトルの積を収束するまで繰り返し行えば良い。そして auth が出てきたら hub は一回の計算で出てくる。

先ほどの隣接行列での計算例。 はこうなる。



で、下記を繰り返し計算する。



結果はこうなる。



一番 Authority score が高いのが 4 番のページ(0.5)で、一番 Hub score が高いのが 0 番のページ(0.366)となる。グラフを再掲しておく。なんとなく納得できるかと。



なお、x も y も正規化している（要素の合計で割るだけ）。

サンプルプログラム

確認のために perl で作ったプログラムとその実行例をあげておく。あくまでサンプルプログラムなので高速化の余地はたくさんある（そもそも行列サイズが大きいとダメ）。あと、収束判定は面倒なので繰り返し数を固定にしている。

■コード(naive-hits-mini.pl)：

#!/usr/bin/perl
use strict;
use warnings;

my $L_ref = [map {chomp; [split(/\s+/, $_)]} <DATA>];
my $Lt_ref = transpose($L_ref);
my $LtL_ref = multiply($Lt_ref, $L_ref);
print_matrix($LtL_ref);

my $x_ref;
foreach (@$L_ref) {
    push @$x_ref, [1];
}

for (my $i = 0; $i < 20; $i++) {
    $x_ref = normalize(multiply($LtL_ref, $x_ref));
}
print_vector($x_ref);

my $y_ref = normalize(multiply($L_ref, $x_ref));
print_vector($y_ref);

sub transpose {
    my ($m_ref) = @_;
    my @rv;
    for (my $i = 0; $i < @$m_ref; $i++) {
	for (my $j = $i; $j < @{$m_ref->[0]}; $j++) {
	    $rv[$j][$i] = $m_ref->[$i][$j];
	    $rv[$i][$j] = $m_ref->[$j][$i];
	}
    }
    return \@rv;
}

sub multiply {
    my ($m1_ref, $m2_ref) = @_;
    my @rv;
    for (my $i = 0; $i < @$m1_ref; $i++) {
	for (my $j = 0; $j < @{$m2_ref->[0]}; $j++) {
	    for (my $z = 0; $z < @$m2_ref; $z++) {
		$rv[$i][$j] += $m1_ref->[$i][$z] * $m2_ref->[$z][$j];
	    }
	}
    }
    return \@rv;
}

sub normalize {
    my ($v_ref) = @_;
    my @rv;
    my $sum = 0;
    foreach my $i (@$v_ref) {
	$sum += $i->[0];
    }
    foreach my $i (@$v_ref) {
	push @rv, [$i->[0] / $sum];
    }
    return \@rv;
}

sub print_vector {
    my ($m_ref) = @_;
    print join("\n", map {sprintf "%.4f", $_->[0]} @$m_ref), "\n\n";
}

sub print_matrix {
    my ($m_ref) = @_;
    print join("\n", map {"@$_"} @$m_ref), "\n\n";
}

__DATA__
0 0 1 0 1 0
1 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 0

■実行例：上から、, auth, hub。

% ./naive-hits-mini.pl
1 0 0 0 0 0
0 0 0 0 0 0
0 0 2 1 1 0
0 0 1 1 0 0
0 0 1 0 3 0
0 0 0 0 0 0

0.0000
0.0000
0.3660
0.1340
0.5000
0.0000

0.3660
0.0000
0.2113
0.0000
0.2113
0.2113

データは前述のもの()を使っている。結果も前述のと同じとなった。

参考文献

この本の記法、式展開、サンプルを使用させて頂きました。PageRankの本なのですが、HITSの解説が分かりやすいです。
- Google PageRankの数理 --最強検索エンジンのランキング手法を求めて--


本記事の数式および図は Google Chart API を使用しています。
- #google - chart API で数式表示 (404 Blog Not Found)
http://blog.livedoor.jp/dankogai/archives/51299017.html
- Google Chart API で Graphviz が使える！すごい！[2011-02-15-3]

その他の参考文献：
- Wikipedia:HITS algorithm
- HITS, 主成分分析, SVD (naoyaのはてなダイアリー)
http://d.hatena.ne.jp/naoya/20090301/hits
（IIRでもやりました。）