PDL で PageRank

id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。

PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。

色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。

さて、PDL を使った PageRank 計算のコードは以下のようになりました。

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

package PageRank;
use base qw/Class::Accessor::Lvalue::Fast/;

__PACKAGE__->mk_accessors(qw/adj_matrix initial_vector alpha iteration/);

use PDL;
use List::Util;

sub calc_eigenvector {
    my $self = shift;
    my $dim = scalar @{$self->adj_matrix};

    for my $row (@{$self->adj_matrix}) {
        my $sum = List::Util::sum @$row;
        $_ = $_ / $sum for @$row;
    }

    ## create Randam Walk vector
    my $r_vec = [];
    for (my $i = 0; $i < $dim; $i++) {
        $r_vec->[$i] = (1 - $self->alpha) * (1 / $dim);
    }
    $r_vec = transpose pdl $r_vec;

    my $P   = transpose pdl $self->adj_matrix;
    my $vec = transpose pdl $self->initial_vector;

    ## Power Method
    for (my $i = 0; $i < $self->iteration; $i++) {
        $vec = $self->alpha * $P x $vec + $r_vec;
    }

    return $vec;
}

package main;
use Perl6::Say;

my $pr = PageRank->new;
$pr->adj_matrix = [
    [ 0, 0, 1, 1 ],
    [ 0, 0, 1, 1 ],
    [ 1, 1, 0, 0 ],
    [ 0, 1, 1, 0 ],
];

for my $alpha (1.0, 0.8, 0.5, 0) {
    $pr->initial_vector = [1, 0, 0, 0];
    $pr->alpha = $alpha;
    $pr->iteration = 50;

    printf "alpha: %f", $alpha;
    my $v_eigen = $pr->calc_eigenvector;
    say $v_eigen;
}

出力は

alpha: 1.000000
[
 [0.16666667]
 [0.27777778]
 [0.33333333]
 [0.22222222]
]

alpha: 0.800000
[
 [0.17857143]
 [0.27040816]
 [0.32142857]
 [0.22959184]
]

alpha: 0.500000
[
 [ 0.2]
 [0.26]
 [ 0.3]
 [0.24]
]

alpha: 0.000000
[
 [0.25]
 [0.25]
 [0.25]
 [0.25]
]

となりました。(alpha はランダムウォークの確率を決める係数です) リンク解析と周辺の話題 のスライドに出てくる例と同じ結果となりました。正しく計算できているようです。

その後調べてみたところ CPAN には Algorithm::PageRank というモジュールがあり、こちらも PDL で計算を行っていまして、自分が書いたものと似たようなコードになっていることがわかりました。PDL で HITS を計算する Algorithm::HITS なども見つかりました。

PageRank と聞くと何か仰々しい物を想像してしまうのですが、小さな行列に対してはこの程度のコードで計算できてしまいます。

PageRank の計算に関するうんちく

PageRank がこの程度のコードで計算できてしまうのは、PageRank の計算がウェブグラフを表現した確率行列の主固有ベクトルを求めることに等しく、またそこで「べき乗法」が使えるのが理由です。

PageRank はランダムサーファーモデルによりウェブグラフの既約性と非周期性を満たすことで、マルコフ過程にある確率推移行列にエルゴード性を見出します。これにより、確率行列は一定時間の後、定常状態に収束することになります。

また、確率行列は主固有ベクトルとして固有値が 1 の固有ベクトルを持ちます。主固有ベクトル以外のベクトルは固有値が 1 未満です。ということは、任意のベクトルを固有ベクトルの一次結合で表現してから線形写像を繰り返すと、固有値1以外の固有ベクトルは近似により消えてなくなってしまいます。(例えば λ = 0.8 の固有ベクトルに写像を3回繰り返すと A3v = λ3v = (0.8)3v となり、乗数の極限を取ると 0 になる。) つまり、そもそも固有値1以外のベクトルを考える必要がない、ということです。

これらの性質を利用するとウェブグラフの確率行列と任意の初期ベクトルとの積を何度も繰り返すだけで主固有ベクトルすなわち PageRank を求めることができます。べき乗法による PageRank の計算についての解説は アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編) がとても分かりやすかったです。

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)

参考文献