ScoreTable L(num_vertices(g));
  L = calc_L(g);                      // shortest path length を計算  
  for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { // 逆数の総和を求める
    score[*vi] = 1 / L[*vi];
  }  		   
		 

PageRankの計算は，厳密にはことなるが基本として Eigenvector Centralityの計算に近い．この計算では，結合した集団の中でつながりを通じて確率的に移動する粒子を仮定して，その集団内での粒子の存在確率を求める指標である．つまり，この値が高いノードとは，Webサイトでいうならば訪問者が多いだろうということになります．PageRankの場合は，リンクのみの移動制約を外してランダムに移動可能な粒子の割合を仮定しています．

  // 各ノードに初期値(1/N)を配布する. 
  ScoreTable score(num_vertices(g), 1.0 / (float)num_vertices(g));
  while(true) {
    float cache = 0.0;
    ScoreTable nv(num_vertices(g), 0.0); // ランダム移動の計算のためのバッファ
    for(tie(vi, vi_end) = vertices(g); vi != vi_end; vi++) {
      float num = (float)out_degree(*vi, g);
      // 自身の現在持っている値の0.85を近接ノードに均等に割り振る
      if(num == 0.0)
	cache += score[*vi];
      else {
	AIter ai, ai_end;
	for(tie(ai, ai_end) = adjacent_vertices(*vi, g); ai != ai_end; ai++)
	  nv[*ai] += (score[*vi] * 0.85) / num;
        // 均等配分をキャッシュにためる
	cache += score[*vi] * 0.15;
      }
    }
    float total = 0.0;
    for(tie(vi, vi_end) = vertices(g); vi != vi_end; vi++) {
      nv[*vi] += (cache / (float)num_vertices(g));
      // 全体の変化量をひろう
      total += (nv[*vi] - score[*vi]) * (nv[*vi] - score[*vi]);
      score[*vi] = nv[*vi];
    }
    if((total * 1000.0) < 0.0000001)  // 変化が乏しくなったら収束したとする
      break;
  }
  return score;		   
	         

Betweenness Centrality は，あるノードからの距離をはかり，一番遠くにあるノードから，近接ノードのなかで距離の近いところにあるノードに水を流すように値を渡していく．これで，ほぼ，nm (nはノード数,mはエッジ数)に計算量が押さえられるはず．といっても，経路の数を数えるために 2nm になっているが．

  for(tie(vi, vi_end) = vertices(g); vi != vi_end; vi++) {
    if(out_degree(*vi, g) == 0 || (int)out_degree(*vi, g) == (int)(num_vertices(g) - 1))
      continue;
    DistTable d(num_vertices(g), 0);
    // 対象とするノードから全てのノードへの距離を測るための探索
    breadth_first_search(g, *vi, visitor(distance_recorder(&d[0])));
    int diameter = 1;
    // 距離の遠い順にノードを並べる
    for(tie(vi2, vi2_end) = vertices(g); vi2 != vi2_end; ++vi2) {
      if(*vi == *vi2 || d[*vi2] == 0)
	continue;
      if(diameter < (int)d[*vi2]) {
	diameter = (int)d[*vi2];
	break;
      }
    }
    if(diameter > 1)      
      check_betweenness(1.0, d, b, g, diameter); // betweennessの計算
  }
  for(tie(vi, vi_end) = vertices(g); vi != vi_end; vi++) {
    score[*vi] = b[*vi]/ ((((float)num_vertices(g)) * ((float)num_vertices(g) - 2.0)) / 2.0);
  }
		 

check_betweenness(float value, DistTable d, ScoreTable& b,
			const SocialNetwork sn, int diameter) {
  AIter ai, ai_end;
  map betweenness;
  map d_table;       //最短パス長が同じノードのリスト

  VIter it, it_end;
  for(tie(it, it_end) = vertices(sn); it != it_end; it++){
    if(d[*it] < 1)                   //同じ距離にあるノードをまとめる作業
      continue;
    d_table[d[*it]].push_back(*it);
    if(diameter < (int)d[*it]) {
      diameter = (int)d[*it];
    }
  }
  for(int i = diameter; i > 1; i--) { //
    VerticesL vertices = d_table[i];
    while(!vertices.empty()) {
      Vertex v = vertices.front();
      int num = 0;
      // 条件(現在のノードの最短パス長より短いノード)にあう近接ノードの数を求める		
      for(tie(ai, ai_end) = adjacent_vertices(v, sn); ai != ai_end; ai++)
	if(d[v] > d[*ai])
	  num++;
      // 現在のノードがもつ betweenness の値に１を足して num で割った値を追加する
      for(tie(ai, ai_end) = adjacent_vertices(v, sn); ai != ai_end; ai++) 
	if(d[v] > d[*ai]) {
	  betweenness[*ai] += (betweenness[v] + 1.0) / (float)num;
	}
      vertices.pop_front();
    }
  }
  for(tie(it, it_end) = vertices(sn); it != it_end; it++) {
    b[*it] += betweenness[*it];
  }		   
		 

betweenness の計算に関しては，ライブラリが用意されており，こちらでは edge_betweenness なども計算できるので便利?

#include 
#include 
#include 
#include 		   
		 

上三つはこれまでと同じ

続いてノードの定義とグラフクラスの準備

struct Node : public std::vector {
  int id;
  enum Type { Exit, Junction } type;
  Node(int _id) : id(_id), type(Junction) {}
  bool remove(Node*);
 private:
  Node();
};

typedef std::vector nodes_t;

class Graph : public std::map {
 public:
  Graph(std::istream&);
  ~Graph();
  const nodes_t& getExits() const { return exits; }
  bool remove(Node*);

  void dump(std::ostream&) const;

 private:
  Graph();
  Node* allocate(int);

  nodes_t exits;
  std::vector nodes;
};
		 

つづいて，betweenness の計算．

いろいろやっているが，見たところ，近接関係グラフ (adacency list)のデータを基に計算をして， associative_property_map に結果を放り込んでいるだけの様子．

void betweeness(const char* filename, Graph& graph) {

  using namespace boost;
  typedef adjacency_list< vecS, vecS, undirectedS > BoostGraph; //グラフの定義
  const int V = graph.size();

  std::map idMap = id_to_pos(graph);
  BoostGraph bgraph(V);

  // Graph のデータを 	       
  for (Graph::iterator sit = graph.begin(); sit != graph.end(); ++sit) {
    Node *node = sit->second;
    // 近接ノード取りだし			      
    for (Node::const_iterator nit = node->begin(); nit != node->end(); ++nit) {
      const Node* other = *nit;
      if (other->id > node->id) {
	const int fpos = idMap[node->id];
	const int tpos = idMap[other->id];
	add_edge(fpos, tpos, bgraph);
      }
    }
  }

  std::map betweenness;
  boost::associative_property_map< std::map >  betweenness_properties(betweenness);  

  // brandes の betweenness の計算		 
  brandes_betweenness_centrality(bgraph, betweenness_properties);
  // 結果の表示	 
  for (Graph::iterator sit = graph.begin(); sit != graph.end(); ++sit) {
    Node *node = sit->second;
    const int fpos = idMap[node->id];
    debug(3) << node->id << "\t" << betweenness[fpos] << "\n";
  }
}
	         

なお，上記のcodeは，副田さんから提供いただいたものに注釈を加えたものです．