GAP Benchmarkの各プログラムの構成について (pr.cc)

GAP Benchmarkの各プログラムの中身を調べている。sssp.ccについて調べた。

pr: PageRank

とりあえずWikipediaでPageRankについて調べてみる。

ja.wikipedia.org

定義式を眺める：

• : ページAにリンクしているページ$T{n}$のページランク。仮にページAに対して3つのページがリンクしているとした場合、$T{1}$から$T_{3}$までの各ページを表す。
• : ページ$T{n}$に含まれる他ページ（Aでも$T{n}$でもないページ）へのリンクの総数。（注：『他ページ』に内部リンクが含まれるのか否かについてはstub）
• : ダンピング・ファクター。通常0.85に設定されるが、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。（常に）

なるほどお。では、さっそくソースコードを眺めてみよう。

github.com

pvector<ScoreT> PageRankPullGS(const Graph &g, int max_iters,
                             double epsilon = 0) {
  const ScoreT init_score = 1.0f / g.num_nodes();
  const ScoreT base_score = (1.0f - kDamp) / g.num_nodes();
  pvector<ScoreT> scores(g.num_nodes(), init_score);
  pvector<ScoreT> outgoing_contrib(g.num_nodes());
  #pragma omp parallel for
  for (NodeID n=0; n < g.num_nodes(); n++)
    outgoing_contrib[n] = init_score / g.out_degree(n);
  for (int iter=0; iter < max_iters; iter++) {
    double error = 0;
    #pragma omp parallel for reduction(+ : error) schedule(dynamic, 16384)
    for (NodeID u=0; u < g.num_nodes(); u++) {
      ScoreT incoming_total = 0;
      for (NodeID v : g.in_neigh(u))
        incoming_total += outgoing_contrib[v];
      ScoreT old_score = scores[u];
      scores[u] = base_score + kDamp * incoming_total;
      error += fabs(scores[u] - old_score);
      outgoing_contrib[u] = scores[u] / g.out_degree(u);
    }
    printf(" %2d    %lf\n", iter, error);
    if (error < epsilon)
      break;
  }
  return scores;
}