ページランクのメモリに乗る場合の実装

チョイ暇だったので、30分ぐらいで作ってみた。本当はディスク使うからこんな風にstlvector使ってやればいいってもんじゃないんだけど・・・。
検証してないから間違ってるかもしれない。
詳しい解説は・・・後で書くかもしれない。


実装的にはTrustRankとかにも使えるように、初期&一定確率で飛ばすノードを指定できるようにしといた。何にも指定しないと、全部に平等に飛ばす。

C++ソース

pagerank.cpp

#include <iostream>
#include <vector>
using namespace std;

const double EPS = 1e-9;
typedef float number;
typedef vector<vector<int> > adj_t; // 隣接リスト方式で作る
class PageRank {
private:
  int n; // ページ数
  adj_t a; // リンクデータ
  number alpha; // ランダムに飛ぶ確率
  vector<int> initial; // 最初に値を振るノード
  
  inline double sq(double x) { return x*x; }
  double diff(const vector<number>& prev, const vector<number>& cur) {
    double ret = 0.0;
    for (int i = 0; i < n; i++)
      ret += sq(cur[i]-prev[i]);
    return ret;
  }
public:
  PageRank(int n, number alpha): n(n), a(n), alpha(alpha) {
    for (int i = 0; i < n; i++) initial.push_back(i);
  }
  PageRank(int n, number alpha, vector<int> initial): n(n), a(n), alpha(alpha), initial(initial) {}
  void add_link(int from, int to) {
    a[from].push_back(to);
  }
  vector<number> calc() {
    //シーケンシャルアクセス用にソートしておく。(HDでは重要、今回はほぼ意味なし)
    for (int i = 0; i < n; i++) sort(a[i].begin(), a[i].end());
    
    const int ini_size = initial.size();
    const number beta = 1.0/ini_size; // ベータはつまりこういう意味
    vector<number> prev(n), cur(n, beta);
    do {
      cur.swap(prev);
      cur.clear();
      cur.resize(n);
      for (int i = 0; i < n; i++) {
        const int size = a[i].size();
        const double val = 1.0/size * (1.0-alpha);
        for (int j = 0, ; j < size; j++)
          cur[a[i][j]] += prev[i]*val;
      }
      const number alphabeta = alpha*beta;
      for (int i = 0; i < ini_size; i++)
        cur[initial[i]] += alphabeta;
      
      //for debug
      for (int i = 0; i < n; i++) cerr<<prev[i]<<" "; cerr<<endl;
    } while (diff(prev,cur) > EPS);
    return cur;
  }
};

int main() {
  const number alpha = 0.15;
  int n; cin>>n; // ノード数
  PageRank pr(n, alpha);
  for (int i = 0; i < n; i++) {
    int m; cin>>m;
    assert(m > 0); // 終端ノードがないことを保障
    for (int j = 0; j < m; j++) {
      int k; cin>>k;
      pr.add_link(i,k);
    }
  }
  vector<number> result = pr.calc();
  number sum = 0.0;
  cout<<"\nresult:"<<endl;
  for (int i = 0; i < result.size(); i++) {
    sum += result[i];
    cout<<result[i]<<endl;
  }
  cout<<"sum="<<sum<<endl; // 1にならないとおかしい
  return 0;
}

入力データ例

input.txt

4
3 1 2 3
2 2 3
2 1 3
1 0

形式はこんな感じ

n
m1 k_1,1 k_1,2 ... k_1,m1
m2 k_2,1 k_2,2 ... k_2,m2
 .                     .
 .                     .
 .                     .
mn k_n,1 k_n,2 ... k_n,mn

nはページ数で番号は0からn-1までで振られる。
mi[i=1,2,...,n]は各ページがリンクしているページ数で、
k_i,j[j=1,2,...,mn]は指しているページ番号。
注意点としてmiは1以上じゃないといけない。これは、どこにもリンクしてないページはダメだよってこと。実用でもこういうのを取り除いて計算してから、取り除いたページは計算が終わった後で、元の位置に戻してうまく値を割り振るってことが行われたりする。
まぁ、これを取り除かないで、イテレーションのたびに合計が1になるように正規化する手法もあるんだけど。

実行例

$./pagerank < input.txt
0.25 0.25 0.25 0.25
0.25 0.214583 0.214583 0.320833
0.310208 0.199531 0.199531 0.290729
0.28462 0.210193 0.210193 0.294994
0.288245 0.207474 0.207474 0.296806
0.289785 0.207346 0.207346 0.295523
0.288694 0.207728 0.207728 0.29585
0.288972 0.207581 0.207581 0.295865
0.288986 0.207597 0.207597 0.295819
0.288946 0.207608 0.207608 0.295837

result:
0.288961
0.207602
0.207602
0.295835
sum=1

追記

同じ研究室の友達の検証によるとあっていたっぽい。よかった。
ちなみに、このinitialにページ一個だけ渡してやるとPersonalRankというのになるらしい。