PHP で Google 第一回 Google の PageRank を PHP で実装

Google の検索エンジンがページのランク付けのために PageRank という指標を使っているというのは聞いたことがあるかと思います。
今日はそのアルゴリズムを PHP で軽めに実装してみました。
ちなみに PHP で実装しても何もいいことがないので、やめたほうがいいでしょう。

まず PageRank というのは簡単に説明すると、 Google が考案したページのランク付けアルゴリズムでページへリンクがそのサイトの評価だという視点でランク付けを行うために作られたものです。
詳細については Google の秘密 - PageRank 徹底解説を参考にしてみて下さい。

その内部アルゴリムですが、おおざっぱにいえば下の箇条書きにあるよう生成された確率行列の、最大固有値（確率行列はだいたいの場合において1）の固有ベクトルをべき乗法で求めることになります。

なぜ確率行列の主固有ベクトルを求める問題に置き換えることができるかと言うと、求めたいものはユーザーがページからページへのリンク移動して対象のサイトに辿り着く確率の合計で、その推移確率の最終的な状態を求めることに確率行列の主固有ベクトルを求める問題は等しいからです。

気をつけけないといけないのは、確率遷移にランダムサーファーモデルをいれることです。これは確率行列の漸近の際に値が収束する（エルゴード性を満たす）ため・ユーザーがページの遷移の際にまったく違うページに移動する可能性を考慮するために行っています。

以下のような流れになります（中の値についてはコードと関係がありません）。

1. 対象のウェブサイトのページリストを生成（A, B, C, Dというページがある！）
2. ページリストから正方行列（二次元配列）を生成
3. n行のサイトが貼ったリンクのサイトの列に1をセット

4. n行のサイトが貼ったリンクのサイトの列に1÷n行のサイトが貼った全体のリンク数（上の1を足し合わせた数）をセット（リンクが多ければ遷移する確率）

5. 正方行列を転置（被リンク数をみるため）

6. 行列を適当な回数べき乗（行列計算の積は以下のようになるので PageRank でいうところの評価の高いサイトからの評価は高いということになる）

7. エルゴード性から値が収束するので、行の値を足すことでそのサイトの PageRank が求められる

実際に以下のように PHP を組み実行してみました。結果は以下のようになっておりリンク解析と周辺の話題と同じ結果になりました。

alpha:1.0
Array
(
    [0] => 0.16666666666667
    [1] => 0.27777777777779
    [2] => 0.33333333333333
    [3] => 0.22222222222221
)
alpha:0.8
Array
(
    [0] => 0.17857142857143
    [1] => 0.27040816326531
    [2] => 0.32142857142857
    [3] => 0.22959183673469
)
alpha:0.5
Array
(
    [0] => 0.2
    [1] => 0.26
    [2] => 0.3
    [3] => 0.24
)
alpha:0.0
Array
(
    [0] => 0.25
    [1] => 0.25
    [2] => 0.25
    [3] => 0.25
)

<?php
$itr = 50;

$i_m = array(0=>array(0.25, 0, 0, 0),
             1=>array(0.25, 0, 0, 0),
             2=>array(0.25, 0, 0, 0),
             3=>array(0.25, 0, 0, 0));

$a_m = array(0=>array(0, 0, 1, 1),
             1=>array(0, 0, 1, 1),
             2=>array(1, 1, 0, 0),
             3=>array(0, 1, 1, 0));

echo "alpha:1.0\n";
print_r(get_picopagerank($i_m, $a_m, 1.0, $itr));
echo "alpha:0.8\n";
print_r(get_picopagerank($i_m, $a_m, 0.8, $itr));
echo "alpha:0.5\n";
print_r(get_picopagerank($i_m, $a_m, 0.5, $itr));
echo "alpha:0.0\n";
print_r(get_picopagerank($i_m, $a_m, 0.0, $itr));
exit;

function get_picopagerank($i_m, $a_m, $alp, $itr) {
  $m = calc_eigenvector($i_m, $a_m, $alp, $itr);
  $p = array();
  for($i = 0; $i < count($m); $i++) {
    $p[$i] = array_sum($m[$i]);
  }
  return $p;
}

function calc_eigenvector($i_m, $a_m, $alp, $itr) {
  $dim = count($a_m[0]);
  for($i = 0; $i < $dim; $i++) {
    for($j = 0, $sum = array_sum($a_m[$i]); $j < $dim; $j++) {
      $a_m[$i][$j] = $a_m[$i][$j] / $sum;
    }
  }

  $r_m = array();
  for($i = 0; $i < $dim; $i++) {
    for($j = 0; $j < $dim; $j++) {
      $r_m[$i][$j] = $j == 0 ? (1 - $alp) * (1 / $dim) : 0;
    }
  }

  $p_m = get_mat_trn($a_m);
  $v_m = get_mat_trn($i_m);

  for($i = 0; $i < $itr; $i++) {
    $v_m = get_mat_dot($p_m, $v_m);
    $v_m = get_n_m_dot($v_m, $alp);
    $v_m = get_mat_pls($v_m, $r_m);
  }

  return $v_m;
}

function get_n_m_dot($a_m, $num) {
  $dim = count($a_m);

  for($i = 0; $i < $dim; $i++) {
    for($j = 0; $j < $dim; $j++) {
      $a_m[$i][$j] = $a_m[$i][$j] * $num;
    }
  }

  return $a_m;
}

function get_mat_pls($a_m, $b_m) {
  $dim = count($a_m);

  for($i = 0; $i < $dim; $i++) {
    for($j = 0; $j < $dim; $j++) {
      $a_m[$i][$j] = $a_m[$i][$j] + $b_m[$i][$j];
    }
  }

  return $a_m;
}

function get_mat_dot($a_m, $b_m) {
  $result = array();  
  $d_a    = count($a_m);
  $d_b    = count($b_m);

  for($i = 0, $a_x = 0, $b_y = 0; $i < ($d_b * $d_b); $i++) {
    $a_x = intval($i % $d_a);
    $b_y = intval($i % $d_b);
    $b_x = intval($i / $d_b);
    for($a_y = 0; $a_y < $d_a; $a_y++) {
      $result[$a_y][$a_x] += $a_m[$a_y][$a_x] * $b_m[$b_y][$b_x];
    }
  }

  return $result;
}

function get_mat_trn($m_m) {
  $result = array();
  $dim    = count($m_m);

  for($i = 0; $i < $dim; $i++) {
    for($j = 0; $j < $dim; $j++) {
      $result[$j][$i] = $m_m[$i][$j];
    }
  }

  return $result;
}

PageRank を理解するにあたっては Google の秘密 - PageRank 徹底解説をまず読みました。その後に PDL で PageRank - naoyaのはてなダイアリーやリンク解析とか: 重要度尺度と von Neumann カーネル - smly’s notepad を参考にコードを書きなどしました。行列については、「マンガでわかる線形代数」を読んで勉強しました（おもしろい！）。また全体の把握については「アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ―超入門編)」がよかったです。

なお PageRank についてはまだ私は読んでいないのですが、 Google の PageRank に関する参考書 - 生駒日記などがあるそうで、よかったら参考にしてみて下さい。

書いておいてあれですが、一部理解できていないところなどあるので、マルコフ連鎖などの基本的な教科書を読んで勉強してみたいと思います。何かおすすめありますでしょうか。