DouKaku?

ページランク - Wikipediaを求めるプログラムを作ってください。(PageRankはGoogleの商標です)

詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると

1. ページがn枚ある場合、n×nの2次元配列を用意する。
2. ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
3. 行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
4. 出力された固有ベクトルから合計が1になるようなPageRankを算出する

という流れになります。

Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので 何百行ものコードになってしまった場合は きっとお題の趣旨から外れていると思います。 このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、 自力で固有値の計算を実装することは求められていません。

data = {
    1: [2, 3, 4, 5, 7],
    2: [1],
    3: [1, 2],
    4: [2, 3, 5],
    5: [1, 3, 4, 6],
    6: [1, 5],
    7: [5],
}

?????

print pagerank
# [0.303514376997, 0.166134185304, 0.140575079872,
#  0.105431309904, 0.178913738019, 0.0447284345048,
#  0.0607028753994]

このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。

PDLで楽勝と思いきや、PDL::eigens()がasymmetric matricesをサポートしていないというショボーンな結果に。他にもいろいろ探して、自前eigen()を実装しようかと思いきや。Inline::Octaveなんちゅう超ど真ん中ストライクなものが！ おかげで超楽勝。なにせPageRank計算部分はGoogle の秘密 - PageRank 徹底解説モロままだけど、Inline::Octave見つけるまでに遠回りし過ぎ。

Dan the Inline::Hacker

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#!/usr/local/bin/perl
use strict;
use warnings;
use Inline Octave => 'DATA';

sub links2matrix{
    my $table = shift;
    my $dim = @$table;
    my $mat = [];
    $mat->[$_] = [(0) x $dim] for (0..$dim-1);
    for my $i (0..@$table-1){
        my $nlinks = scalar @{$table->[$i]};
        $mat->[$_-1][$i] = 1/$nlinks for (@{$table->[$i]});
    }
    $mat;
}

my $m = Inline::Octave->new(
    links2matrix(
        [
            [ 2, 3, 4, 5, 7 ],
            [ 1],
            [ 1, 2 ],
            [ 2, 3, 5 ],
            [ 1, 3, 4, 6 ],
            [ 1, 5 ], [5],
        ]
    )
);
local $\ = "\n";
print "Matrix:";
print $m->disp();
print "Pagerank:";
print pagerank($m)->disp();
__DATA__
__Octave__
function p=pagerank(m);
[v,d] = eig(m);
ev = v(:, find(abs(diag(d)) == max(abs(diag(d)))));
p = ev ./ norm(ev, 1);
endfunction