推移確率行列と確率ベクトル
こう考えてみましょう。大量のビー玉を例えばページ0に流し込みます。ビー玉はリンクに沿って転がり、リンク先ページに辿り着きます。ページ0に置かれたビー玉はページ1と2に、半数ずつ転がっていくでしょう。ページ1に辿り着いたビー玉はすべてページ3へ、ページ2に辿り着いたビー玉はさらに半数ずつに分かれてページ1と4に転がります。十分長い時間が経過したのち、各ページにあるビー玉の個数を勘定すれば、ページにあるビー玉の数÷ビー玉の総数は各ページにどのくらいの確率でビー玉が存在するかを意味します。これが大きいということは、それだけそのページに人気がある、すなわちPagerankになるんじゃないかと。
各ページのビー玉存在確率を計算する実装を考えましょう。リンクに重みを付けたページ群を行列で表現します。8つのページそれぞれから自分自身を含めて8通りの行先（リンク）が張れるので8行8列の行列：Hを用意します。
ページcからページrに向かう重さpのリンクに対応して、r行c列の要素H[r][c]の要素をpとします（リンクのない要素についてはp=0）。そうすると行列Hの各列には列に対応するページから他のページに辿り着く確率が縦にならびますよね（なので各列の合計はどれも1）。この行列を"推移確率行列"と呼ぶそうな。
そしてもう一つ、ベクトルIを用意します。Iの長さ（要素数）はページ数と同じ、I = { P0, P1, …… }は、ページiに確率Piでビー玉があることを示します（もちろんPiの総和は1）。確率の並びであることから、このベクトルを"確率ベクトル"というんだってさ。
ここでHとIの積を求めるとページ群のリンクを一回だけ辿ったときの確率ベクトルつまり各ページのビー玉存在確率が求まります。
ベクトルと行列、および行列とベクトルの積を定義します。
// vec<T,N> : T型のN行ベクトル
template<typename T,size_t N>
using vec = std::array<T,N>;
// mat<T,M,N> : T型のM行N列行列
template<typename T, size_t M, size_t N>
using mat = std::array<vec<T,N>,M>;
// 行列とベクトルの積 : vec = mat * vec
template<typename T, size_t M, size_t N>
vec<T, M> operator*(const mat<T, M, N>& m, const vec<T, N>& v) {
vec<T,M> result;
for (int r = 0; r < M; ++r) {
// mのr行 と v の内積
result[r] = std::inner_product(v.begin(), v.end(), m[r].begin(), T(0));
}
return result;
}
streamへの出力などモロモロのヘルパ関数を定義して実際に計算してみましょう。ひとまずI = { 1, 0, 0, 0, 0, 0, 0, 0 }、つまりページ0にすべてのビー玉を置き、リンクを辿って転がしたときの各ページのビー玉存在確率を求めることになります。I = H * Iを30回繰り返すコードがコチラ：
#include <array>
#include <algorithm>
#include <numeric>
#include <iostream>
// vec<T,N> : T型のN行ベクトル
template<typename T,size_t N>
using vec = std::array<T,N>;
// mat<T,M,N> : T型のM行N列行列
template<typename T, size_t M, size_t N>
using mat = std::array<vec<T,N>,M>;
// ベクトルのstreamへの出力
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& stream, const vec<T, N>& v) {
bool first = true;
for ( const T x : v) {
if (!first) { stream << ", "; }
stream << x;
first = false;
}
return stream;
}
// 行列のstreamへの出力
template<typename T, size_t M, size_t N>
std::ostream& operator<<(std::ostream& stream, const mat<T, M, N>& m) {
for ( int r = 0; r < M; ++r ) {
stream << m[r];
if ( r != M-1 ) stream << std::endl;
}
return stream;
}
// 確率ベクトルを作る: v(N行ベクトル)の非0要素を 1/(非0要素数) にする
// (要素の総和は1となる)
template<typename T, size_t N>
void stochastic(vec<T, N>& v) {
// 非0要素数をnに求め
int n = std::count_if(v.begin(), v.end(), [](T x) { return x != T(0);});
// 非0要素を 1/n にする
for ( T& x : v ) { if ( x != T(0) ) x = T(1)/n; }
}
// 転置行列(行と列を入れ替える)
template<typename T, size_t M, size_t N>
mat<T, N, M> transpose(const mat<T, M, N>& m) {
mat<T,N,M> result;
for (int r = 0; r < M; ++r) {
for (int c = 0; c < N; ++c) {
result[c][r] = m[r][c];
}
}
return result;
}
// 行列とベクトルの積
template<typename T, size_t M, size_t N>
vec<T, M> operator*(const mat<T, M, N>& m, const vec<T, N>& v) {
vec<T,M> result;
for (int r = 0; r < M; ++r) {
// mのr行 と v の内積
result[r] = std::inner_product(v.begin(), v.end(), m[r].begin(), T(0));
}
return result;
}
int main() {
using namespace std;
typedef mat<float,8,8> Mat;
typedef vec<float,8> Vec;
// 0 1 2 3 4 5 6 7
Mat H = { Vec { 0,1,1,0,0,0,0,0 }, // ページ0 から 1, 2 へのリンク
Vec { 0,0,0,1,0,0,0,0 }, // ページ1 から 3 へのリンク
Vec { 0,1,0,0,1,0,0,0 }, // ...以下同文
Vec { 0,1,0,0,1,1,0,0 },
Vec { 0,0,0,0,0,1,1,1 },
Vec { 0,0,0,0,0,0,0,1 },
Vec { 1,0,0,0,1,0,0,1 },
Vec { 0,0,0,0,0,1,1,0 } };
for ( auto& v : H ) { stochastic(v); } // 各行を確率ベクトルに変換し
H = transpose(H); // 転置する
cerr << H << endl << endl;
// 確率分布I の初期状態から I = H*I を何度か繰り返す
Vec I = { 1, 0, 0, 0, 0, 0, 0, 0 };
for ( int i = 0; i < 30; ++i ) {
cout << I << endl;
I = H * I;
}
cout << I << endl;
}
実行結果をCSVファイルにリダイレクトし、Excelに食わせてみました。
最初ページ0にあったビー玉が半数ずつページ1と2へ、さらにそこから1、3、5へと次第に拡散していく様子が見て取れます。
各列の値の推移をグラフにすると、
ご覧のとおり、ビー玉の存在確率は一定の割合に収束するんです。
これは初期値を変えても同じこと、ページ1からスタートした場合/全ページ等確率（1/8）からスタートした場合もやってみました。
I = H * Iを何度も繰り返して得られた確率ベクトルIは「たくさんの人がこのページ群のリンクを辿ったときに行きつくページの確率」なわけで、この値をキーに大きい順にソートしたページ列がGoogleの検索結果になるってスンポーです。
