HITS とはハイパーリンク構造（リンクや被リンクなど）を用いてウェブページのスコアを計算する方法。Google で用いられている PageRank の仲間。
HITS は Authority score(以下、auth) と Hub score(以下、hub) の2種類のスコアを算出する。
アルゴリズム概要
各ページiの持つ auth を
実例で解説。下図のようなウェブグラフがあるとする。
初期値
| 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 |
表の見方：
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でもやりました。）
この記事に言及しているこのブログ内の記事