グラフのuniform expected rankを計算するプログラム
evcalc ver 0.2a

• グラフが与えられたときに、その各辺が確率pで故障することを考える。 このとき、ある特定の頂点vに対して、vから故障していない辺をたどって行ける頂点の個数(v自身は除く)の期待値をexpected rank ER(G,v; p)と呼ぶ。これをpについて0〜1で積分した値をuniform expected rank u-ER(G,v)と呼ぶ。
  このプログラムは、このuniform expected rankを各頂点について計算する。 ただし、正確計算は困難であるため、モンテカルロ法を用いて近似値の計算をする。
   
• コンパイル(以下unixで、%のマークはコマンド・プロンプトのつもり)
  1. 解凍する。GNUのtarがある場合は
     % tar xfz evcalc-0.1.tar.gz
     GNUじゃないtarの場合は
     % gunzip -c evcalc-0.1.tar.gz | tar xf -
     で evcalc-0.1 というディレクトリができる。
  2. できたディレクトリに移って
     % make
     
  3. evcalc というバイナリが出来る。
  (Cで書いてあるので、Cのコンパイラが必要。(MakefileはGCCでのコンパイルを想定してあります。))
   
• データファイル
  このプログラムの計算はグラフは連結なものと仮定して計算するので、データは連結なグラフのものを用意する。(非連結な場合はあらかじめ連結成分に分けて、それぞれについて計算させて下さい。)
  データファイルはグラフの接続行列をテキストファイルとして用意する。 例えば、次のようなグラフに対してはその下のような内容のファイルを用意する。
  

  6 5
  1 1 0 0 0 
  1 0 1 0 0 
  1 0 0 1 0 
  0 1 0 1 0 
  0 0 1 1 0 
  0 0 0 1 1
  

  最初の1行にある2つの数字は、辺数と頂点数(順番に注意)で、2つをスペースで区切って並べる。 2行目以降は接続行列を、各エントリーをスペースで区切って書く。 接続行列は、行が辺、列が頂点に対応するようにする。 プログラムの中では各頂点はこの隣接行列のインデックスの順に0,1,2,…,n-1とい番号で扱われる。(行(辺)の順番は影響しない。)
   
• 使い方
  1. プログラムをコンパイルする。(上参照。)
  2. データファイルを用意する。(上参照。)
  3. 標準的な実行法： 「evcalc < ファイル名」
     (注：Unixの場合、ファイル名がfile.datのときは「./evcalc < file.dat」というコマンドを実行することになる。)
     のように実行すると、有効数字3桁が確保できるくらいにモンテカルロ法の試行回数を適宜設定して計算する。
     (最初10000回で計算して標準偏差を計算し、これを元に標準偏差が十分小さくなるように回数を設定して再度計算する。)
     出力は、「頂点番号: uniform rankの数値 ( 標準偏差 )」の形で出力される。 (上下に計算上のデータが表示される。最後に出るCOUNTがモンテカルロ法の試行回数、sigmaが標準偏差の最大値。)
     ＃ 15回計算を行ない、その平均値と標準偏差が出力されるようになっている。
  4. 諸オプション
     • evcalc -n N < ファイル名
       モンテカルロ法の試行回数をNに決めて実行する。
     • evcalc -s x < ファイル名
       標準偏差がx以下になるように試行回数を調整して計算する。
     • evcalc -f N < ファイル名
       有効数字N桁が確保できるくらいに試行回数を調整して計算する。
     • evcalc -h
       ヘルプ
  5. 計算例
     上のデータ例で計算させると次のような感じの出力になる。

     1 1 0 0 0 
     1 0 1 0 0 
     1 0 0 1 0 
     0 1 0 1 0 
     0 0 1 1 0 
     0 0 0 1 1 
     
     min value = 2.333756 
     smin = 0.002500 
     v = 0.000061 
     s = 0.007789 
     ---
     s = 0.007789, COUNT = 194139 
     min value = 2.333444 
     smin = 0.002500 
     v = 0.000002 
     s = 0.001484 
     0: 2.242705 ( 0.000511 ) 
     1: 2.092529 ( 0.000537 ) 
     2: 2.092638 ( 0.000662 ) 
     3: 2.333444 ( 0.000415 ) 
     4: 1.695508 ( 0.001484 ) 
     [ COUNT = 194139, sigma = 0.001484, N = 15 ]
     

     入力した接続行列が最初に出力される(データファイルが間違えていないかの確認のため)。
     その後の出力の最初の4行は、最初に10000回の試行で計算したときの値の最小値(min value)、標準偏差の目標上限(0.0025)、分散の最大値(v)、標準偏差の最大値(sigma)。
     ここで出てきたsigmaの値を元に、試行回数COUNTを定めて計算し直す。もう一度同じデータが出力されたあとで、sigmaがsminより小さくなっていたら計算結果が出力される。 (ここでsigmaがsminより大きい場合にはCOUNTを大きくしてもう一度計算しなおされる。)
     (最後の行には、試行回数COUNT、標準偏差の最大値sigmaと、平均と標準偏差の計算のための計算回数N=15がもう一度表示される。)

  ---

  Home