メモ帳

メモ帳です.

Boost Graph Libraryメモ②

Boost Graph Library (BGL)

1つ前の記事 

tomov3.hatenablog.com

でBGLについて少し触れた.

この記事では隣接行列の形でグラフを表現するadjacency_matrixを紹介する.

上の記事で紹介したadjacency_listクラスは,隣接リストグラフ構造を表現するために使用するインターフェースである.

adjacency_matrix

adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>

adjacency_matrixの利点としては,辺の削除や追加が定数時間で終了するという点が挙げられる.

しかし,行列はn×nであり,メモリ消費量が大きいという欠点がある(nはノード数とする).
adjacency_matrixはグラフの密度が高い(辺の本数が多い)場合に向いていて,adjacency_listは密度が低い場合に向いている.

パラメータ

adjacency_matrixにはDirected, VertexProperty, EdgeProperty, GraphProperty, Allocatorという5つのパラメータが存在する.

Directedは有向か無向かを決定し,VertexProperty,EdgeProperty,GraphPropertyはプロパティを設定する.
Allocatorには特に記述がなかったが,おそらくメモリの確保や割り当てを行うオブジェクトのことを意味していると思う.

使用例

例が紹介されていた.

  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";
  
  typedef boost::adjacency_matrix<boost::directedS> Graph;
  Graph g(N);
  add_edge(B, C, g);
  add_edge(B, F, g);
  add_edge(C, A, g);
  add_edge(C, C, g);
  add_edge(D, E, g);
  add_edge(E, D, g);
  add_edge(F, A, g);

  std::cout << "vertex set: ";
  boost::print_vertices(g, name);
  std::cout << std::endl;

  std::cout << "edge set: ";
  boost::print_edges(g, name);
  std::cout << std::endl;

  std::cout << "out-edges: " << std::endl;
  boost::print_graph(g, name);
  std::cout << std::endl;

The output is:

  vertex set: A B C D E F 

  edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A) 

  out-edges: 
  A --> 
  B --> C F 
  C --> A C 
  D --> E 
  E --> D 
  F --> A 

addEdge()で辺を追加し,boost::print_graph()でedge setを出力する.

他にもnum_vertices()で頂点数を,num_edges()で辺の数を得る関数などが用意されている.

さいごに

今後もBGLを使用したプログラムの例などを記事にしたいと思います.PageRank計算を行うプログラムなど,具体的な例を紹介できればと思います.

Boost Graph Libraryメモ

Boost Graph Library (BGL)

C++でグラフを扱うプログラムを作成するために,BGLの勉強を始める. Table of Contents: Boost Graph Libraryを参考にする.

BGLはグラフの構造へどのようにアクセスするかを定めた インタフェースである。グラフ構造はadjacency_listクラスで実装する.

adjacency_list

adjacency_listの詳細は

Boost Graph Library: Adjacency List

に,使い方は

Using the Boost Graph Library

に詳しい記述がある.

adjacency_list<EdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties>
  • EdgeList, VertexListはそれぞれどの種類のコンテナを用いて辺と頂点を表現するかを決定する.

std::vectorを使用する場合はvecS,std::listを使用する場合はlistSを選択する.

  • Directedは有向か無向か,または双方向の辺アクセス (出辺と入辺の両方にアクセス する) の有向かを選ぶ.

有向グラフを選ぶには directedS か bidirectionalS を使い、無向グラフを選ぶには undirectedS を使う。

あとの3つはプロパティを設定する.
それぞれデフォルトはvecS,vecS,directedS,no_property,no_property,no_propertyである.

使用例

family treeをグラフで表現した例が以下に挙げられていた.

http://boost.cppll.jp/HEAD/libs/graph/example/family-tree-eg.cpp

後日実際に実装して新たに記事にしたい.

追記 (2016/6/22)

とても分かりやすいスライドを見つけました.

www.slideshare.net

BGLについて学びたい方にとてもオススメです.

Efficient Ad-hoc Search for Personalized PageRank [SIGMOD'13]

Ad-hocにPersonalized PageRankを計算

グラフはdynamicに変化するため,ad-hocに検索する手法が重要.
この論文は,前処理することなくPersonalized PageRankのtop-kを高速かつ正確に計算する.

問題

Given: Graph G, the scaling parameter c, required number of answer nodes k, and set of query nodes Q.
Find: Top-k nodes exactly where k nodes are arranged in descending order with respect to their PPR scores.

提案手法

イデア

反復計算の各ステップにおいて,

  • 最終的なスコアの上限と下限の推定値をそれぞれ計算する.

  • 推定値に基づき,不必要なノードを取り除いた部分グラフを構築.

  • グラフ全体ではなく,部分グラフに対してのみスコアを計算.

詳細

  • k-th highest lower estimationをεkとしたとき,upper estimationがεkよりも小さいノードは解になり得ない.

  • 部分グラフは,解になり得るノードと,それにi hopで到達可能なノードの集合とする.

実験

Norredame, CNR, Email, Socialの4つのデータセットを使用.

実行速度

  • それぞれ90%, 75%, 85%, 65%ほど削減できた.

  • ノード数が同程度の場合でも,グラフの直径によって実行速度は異なる.

正確性

  • 得られる結果は,オリジナルの手法の結果と一致する.

Flexibility

  • scaling parameterが小さいほど高速

推定値がより正確になるため

Case-Studies

航空データを使用したcase studyが紹介されていた.

  • scaling parameterが小さいほど,locally-orientedとなった.

最初はc=0.5に設定し,locally-orientedにしたいなら値を小さくする.そうでないなら値を大きくするのが推奨されていた.

Efficient Personalized PageRank with Accuracy Assurance [KDD'12]

Personalized PageRank (PPR) の効率的な計算

この論文は,Personalized PageRankの3つの問題を効率的に計算する手法を提案した.
QR分解あたりの証明が難しく,あとで再確認する.

問題

Problem1 (Single-node relevance computation)

Given: Query node x and query distribution d.
Find: Relevance score of node x according to query distribution d.

Problem2 (Top-k nodes identification)

Given: The number of required answer nodes, K, and query distribution d.
Find: Top K nodes with the highest relevance scores with respect to query distribution d.

Problem3 (Highly relevant node detection)

Given: The threshold, ε, and query distribution d.
Find: Nodes whose relevance scores are higher than ε with respect to query distribution d.

提案手法

イデア

  • ベクトルの内積によってsingle node scoreを計算.(Problem1)

  • 最終的なスコアの下限値と上限値を推定し,解になり得るかどうかを判定する.(Problem2, 3)

詳細

Problem1

  • 内積の形に変形するためにQR分解をする.

  • QとRが疎になるように,ノードをpermuteする.

Problem2, 3

  • はじめに全てのノードの下限値を推定.

  • 下限値の降順でノードをたどる.

  • 解になり得ないノードに到達したとき,処理を終了する.

Problem2, 3でノードのスコアが必要になったとき,Problem1のsingle node score計算を利用している.
(説明が雑なので,あとでノートで確認する...)

実験

Table2より,Q,Rが確かに疎になっていることが確認できる.
すべての問題について,良い性能を示した.

Case-Studies

航空データを用いたcase studyが紹介されている.
San Diego, New York, Denver, Orlandoをseed nodeとして,関連の強い都市を検出した.

Fast and Exact Top-k Algorithm for PageRank [AAAI'13]

PageRankにおいて高速かつ正確にTop-kを求める

読んだ論文を忘れないうちにまとめておく.
この論文は,PageRankのTop-k検索を求める手法 F-Rank を提案した.

問題

Given: Arbitrary graph G and required number of answer nodes k.
Find: Top-k nodes with respect to thier PageRank scores exactly and efficiently.

提案手法

イデア

反復計算の各ステップにおいて,

  • ノードの最終的なスコアの上限値,下限値を推定.

  • 推定値に基づいて不必要なノードを枝刈りし,部分グラフを構築.

結果として,計算対象とするグラフのサイズが小さくなり,計算コストが削減される.

詳細

  • 各ステップにおいて,推定値はO(1)でincrementallyに計算可能.
  • 上限値,下限値は本来のスコアに収束する.
  • k-th highest lower bound estimation を εk とすると,upper bound estimationが εk よりも小さいノードは解になり得ない.
  • 解になり得るノードの集合を CCにreachableなノード集合をRとする.スコア計算はR全体に,推定値の計算はCを対象に行う.

実験

P2P,Web,Wikipediaの3種のデータセットを用いる.

実行時間

  • オリジナルのPageRank計算と比較して,それぞれ40%,70%,90%削減された.

正確性

  • オリジナルのPageRankで得られた結果と一致する.

以上より,高速かつ正確な結果が得られることが示された.