WikipediaのキーワードリンクでPageRankを試す

この前のエントリ(WikipediaのキーワードリンクでHITSアルゴリズムを試す - のんびり読書日記)ではWikipediaのキーワードリンクを使ってHITSを実行してみましたが、今回はPageRankを試してみたいと思います。

PageRankの概要はもう説明するまでもないですね。より詳細なアルゴリズムを知りたい方は、下のページを参照してください。

http://homepage2.nifty.com/baba_hajime/wais/pagerank.html

では実際に試してみます。今回作成したコードは以下の通りです。ほとんどの部分が前回のHITSの使いまわしです^^;

#!/usr/bin/perl
#
# PageRank
#
# Usage:
#  pagerank.pl -l linkdb -o pagerankdb
#

use strict;
use warnings;
use Getopt::Long;
use TokyoCabinet;

use constant {
    TMP_DBM   => '/tmp/pagerank_tmp_%d.hdb',
    PROB_JUMP => 0.15
};

sub usage_exit {
    print <<'USAGE';
Usage:
 pagerank.pl -l linkdb -o pagerankdb
   -l, --link linkdb         link structure DBM
   -o, --output pagerankdb   PageRank DBM
USAGE
    exit 1;
}

sub _initialize {
    my ($linkdb, $prdb) = @_;
    my $rnum = $linkdb->rnum();
    my $initval = 1 / sqrt($rnum);
    $linkdb->iterinit();
    while (my $id = $linkdb->iternext()) {
        $prdb->put($id, $initval);
    }
}

sub _fill_zero {
    my ($prevdb, $nextdb) = @_;
    $prevdb->iterinit();
    while (my $id = $prevdb->iternext()) {
        $nextdb->put($id, 0);
    }
}

sub _make_temp_dbm {
    my $count = shift;
    my $prdb = TokyoCabinet::HDB->new();
    if (!$prdb->open(sprintf(TMP_DBM, $count),
        $prdb->OWRITER | $prdb->OCREAT | $prdb->OTRUNC)) {
        die 'cannot open output dbm';
    }
    return $prdb;
}

sub _update_pagerank {
    my ($linkdb, $prevdb, $nextdb) = @_;

=comment
    _fill_zero($prevdb, $nextdb);
    my $jumppoint = 1 / $linkdb->rnum() * PROB_JUMP;
=cut
    $prevdb->iterinit();
    while (my $previd = $prevdb->iternext()) {
        my $prevval = $prevdb->get($previd);
        next if !$prevval;
        my $linkval = $linkdb->get($previd);
        next if !$linkval;
        my %link = unpack('(Nn)*', $linkval);
        next if !%link;
        my $point = $prevval / scalar(keys %link) * (1 - PROB_JUMP);
        foreach my $linkid (keys %link) {
            my $nextval = $nextdb->get($linkid) || 0;
            $nextdb->put($linkid, $nextval + $point);
        }
=comment
        # random jump
        $nextdb->iterinit();
        while (my $nextid = $nextdb->iternext()) {
            my $nextval = $nextdb->get($nextid) || 0;
            $nextdb->put($nextid, $nextval + $jumppoint);
        }
=cut
    }
}

sub pagerank {
    my ($linkdb, $num_loop) = @_;
    my $count = 0;

    print "Start PageRank Algorithm\n";

    print "Initialize PageRank values\n";
    my $prevdb = _make_temp_dbm($count++);
    _initialize($linkdb, $prevdb);

    my $nextdb;
    # 本当は更新前後で比較しないとダメ
    for (my $i = 0; $i < $num_loop; $i++) {
        print "PageRank Loop No.$i\n";

        print " Update PageRank values\n";
        $nextdb = _make_temp_dbm($count++);
        _update_pagerank($linkdb, $prevdb, $nextdb);
        my $prevpath = $prevdb->path();
        $prevdb->close();
        unlink $prevpath;
        $prevdb = $nextdb;
    }
    return if !$nextdb;

    my $nextpath = $nextdb->path();
    if (!$nextdb->close()) {
        die 'DBM error: '.$nextdb->errmsg($nextdb->ecode);
    }
    return $nextpath;
}

sub main {
    my ($opt_link, $opt_output);
    GetOptions(
        'link=s'   => \$opt_link,
        'output=s' => \$opt_output,
    );
    if (!$opt_link || !$opt_output) {
        usage_exit();
    }

    my $linkdb = TokyoCabinet::HDB->new();
    if (!$linkdb->open($opt_link, $linkdb->OREADER)) {
        die "cannot open $opt_link";
    }

    my $dbpath = pagerank($linkdb, 2);
    if ($dbpath) {
        rename $dbpath, $opt_output;
        print "PageRank Result was saved: $opt_output\n";
    }
    else {
        print "Calculating PageRank values failed...orz\n";
    }

    if (!$linkdb->close()) {
        die 'DBM error: '.$linkdb->errmsg($linkdb->ecode);
    }
}

main();

__END__

PageRankがHITSと異なる点で、ノードを移動する際にリンクをたどるだけではなく、関係ないノードにジャンプへの考慮があります。Webのブラウジングで例えると、ページ中のリンクをクリックして移動する以外に、直接URLを入力しての移動や、ブックマークから選択しての移動をPageRankでは考慮して計算を行います。(僕が勘違いしてるだけで、本当はHITSも考慮しているのかもしれませんが)

ただし、上記のソースコードでは処理速度のことを考えて、ジャンプの部分はコメントアウトしています。正直、ジャンプしなくてもそこまで変わらないのでは？と勝手に推測しています。

上記のコードを実行すると、TokyoCabinetのHashDBの形式でPageRankの値を保持したDBMが作成されます。

% ./pagerank.pl -l input/keywordlink.hdb -o output/pagerank.hdb
Start PageRank Algorithm
Initialize PageRank values
PageRank Loop No.0
 Update PageRank values
PageRank Loop No.1
 Update PageRank values
PageRank Result was saved: /home/mizuki/data/wikipedia/pagerank.hdb
% tchmgr list -pv output/pagerank.hdb | sort -k 2 -g -r | head -20
795475  2.49622740425123
774362  1.45601468727367
1026301 1.33406447275745
1115992 0.984013382831156
695574  0.873433579187502
2314    0.820067969010297
745520  0.741864896427095
1205720 0.705696903616374
1154752 0.667709274780219
1188197 0.643424341524438
367227  0.626496363083897
1241052 0.581159578115715
382164  0.55067707678437
3966    0.542766825457455
4385    0.535500192373554
400306  0.533001579629524
975171  0.498391999634851
2740    0.49625364796896
29926   0.471631367047205
1118    0.432997065752846

PageRankが高い上位20位までをキーワードに戻してみます。HITSと同様に地名が多く含まれていますが、「英語」「コムーネ」「小惑星」などいくつか違うキーワードも含まれていますね。というかコムーネってなんだっ。

順位	PageRankが高いキーワード
1	日本
2	東京都
3	アメリカ合衆国
4	イギリス
5	フランス
6	ドイツ
7	英語
8	第二次世界大戦
9	北海道
10	イタリア
11	昭和
12	コムーネ
13	大阪府
14	小惑星
15	株式会社
16	中国
17	明治
18	江戸時代
19	小惑星帯
20	考古学

「女性タレント」カテゴリの上位を調べてみます。

順位	PageRankが高いキーワード
1	工藤静香
2	松田聖子
3	中森明菜
4	和田アキ子
5	中山美穂
6	松浦亜弥
7	榊原郁恵
8	上戸彩
9	BoA
10	斉藤由貴
11	後藤真希
12	椎名林檎
13	森高千里
14	柴咲コウ
15	宮沢りえ

HITSの結果と比べると、「藤原紀香」「篠原涼子」「中川翔子」などがランク落ちし、かわりに「榊原郁恵」「後藤真希」「椎名林檎」などが入っています。うーん、違いは何だろう…？

ただやはりPageRankもHITSも似たような結果が出ますね。HITSはオーソリティとハブの2種類の特徴量を持たせることで、おそらくより精度の高い結果が得られるのだと思いますが、さくっと試すだけならPageRankも楽ちんでいいかなーと思います。