ネットワーク可視化のアルゴリズム

岡本 吉央

概要

ネットワーク可視化のための基本的なアルゴリズムを実装し，アルゴリズム設計と評価の方法論，実装上の注意点を主体的に学ぶ．その中で，ネットワーク，最適化，数値計算，計算幾何学など，様々な分野が有機的に関連している様子を体感する．実装はRubyで行う予定であるが，Rubyに精通している必要はない．また，講義『グラフとネットワーク』を履修している必要もない (が，履修していると理解が深まる)．

ネットワーク可視化，グラフ描画，ばねモデル，ランダム・グラフ，最適化，計算幾何学

イメージ図

レポート提出締切変更

• 新しい締切：11月13日 (木) 13:00
• 提出方法は変わらず
  • メール：プログラムのソース，適当に圧縮して送付すること (圧縮コマンドはgzip, bzip2, tarなどがある)
  • 紙に印刷したもの：普通のレポート
    このレポートの中でプログラムのソースなどを参照する場合は，ファイル名と行番号を明示すること
• 提出先
  • メール： okamotoy@uec.ac.jp (メーリングリストではないので注意)
  • 紙に印刷したもの：西4号館4階 事務室前のレポート提出BOX (「岡本」と書いてあるところ)
• 再提出の場合は，メールで個別に連絡

テキストの訂正

• 8ページ目，164と165の間：「elseはelsifを」→「elseとelsifを」
• 18ページ目，下から3行目：「76行目でアニメーション開始」→「78行目でアニメーション開始」
• 19ページ目，コマンド入力の3つめ：「cp /home3/...」→「cp -r /home3/...」
• 20ページ目，下から4行目：「頂点2と5は隣接していない」→「頂点1と5は隣接していない」
• 22ページ目，式(1)のすぐ下：「$\mathbf{p}_u$を始点とし，$\mathbf{p}_v$を終点とする」→「$\mathbf{p}_v$を始点とし，$\mathbf{p}_u$を終点とする」
• 22ページ目，式(3)：$\{u,v\} \in E$ のとき，「$A_{u,v}=1$」 ではなく，「$A_{u,v}=\frac{1}{\deg(u)}$」
• 22ページ目，式(5)の下：「これは固有値問題である．行列$A$は対称行列なので，その固有値はすべて実数であり，固有ベクトルが頂点の位置に対応する．」→「これは線形方程式であり，$\mathbf{p}$は$A$の固有ベクトル (のようなもの) である．」
• 22ページ目，「Tutteの手法：アルゴリズム」の直前：「この固有値問題を真面目に解くのではなく」→「この線形方程式を真面目に解くのではなく」
• 24ページ目，下から4行目の「Fruchterman-Reingoldの手法：定式化」の囲みの中：「式(8)」→「式(12)」
• 29ページ目，3.2節の13行目冒頭：「$(\|\mathbf{p}_i - \mathbf{p}_j\|-d_{i,j})^2$」→「$(\|\mathbf{p}_i - \mathbf{p}_j\|-c \cdot d_{i,j})^2$」
• 30ページ目，式(18)：「$k_{i,j}$」→「$\displaystyle \frac{k_{i,j}}{2}$」
• 35ページ目，下から10行目：「Step 2-1において式(34)を用いる」→「Step 2-1において式(39)を用いる」
• 35ページ目，式(40)：「$a=-x_u-y_v$, $b=x_v+y_u$」→「$a=y_u-y_v$, $b=x_v-x_u$」
• 35ページ目，下から5行目：「式(34)を用いた計算は」→「式(39)の左辺は$0$となるはずである．しかし，数値計算上の様々な状況により，厳密に$0$となるかどうか分からない．そのため，Step 2における「すべての異なる2辺$e,e' \in E$に対して」において考える$e$と$e'$が端点を共有する場合は，Step 2-1を実行しない方が信頼できる結果が得られる．」

その他

• Rubyにて，文字列strを整数に変えるには「str.to_i」として，文字列strを浮動小数点数に変えるには「str.to_f」とする．
  例："12345".to_i => 12345, "12.345".to_f => 12.345
• CEDにてスクリーンショットを取るには，「Fn」を押しながら「i」を押す．そのとき出てくるウィンドウに従って保存する．
• (10月8日の進捗報告受領確認メールで書いたこと)：Eadesのアルゴリズム (に限らず他のアルゴリズム) の実装について，以下に注意して下さい．
  • Tutteのアルゴリズムにはある $U$ に対応するものはEadesのアルゴリズムにありません． プログラムでいえば，fixed_nodesに対応するものはありません．
  • Tutteのアルゴリズムを実装したサンプルプログラムの説明にも書いてますが，Eadesのアルゴリズムでも，Step 0は実行する必要はありません．グラフを読み込んだときに，ランダムな位置が既に割り当てられるからです．
  • Eadesのアルゴリズムに限らず，他のアルゴリズムも，なかなか収束しないので，適当な反復回数で計算を打ち切って下さい．(アニメーションで見る場合は，ずっと反復させておいてもよいです．)
  • c1, c2, c3, c4というパラメータは資料に書いてある値では，綺麗に図が出ないみたいです．私がいま試した限りでは，例えば，c1 = 0.02, c2 = 0.01, c3 = 0.2, c4 = 0.001だと，一応見ることができるような図は出てきました．他の値だとまた違った図がでるかもしれませんが，皆さんもできるだけよい値を見つけてみて下さい．
• Fruchterman-Reingoldのアルゴリズムでは，頂点が大きく動きすぎる傾向があるので，力$f$に適当な係数をかけてちいさくすれば，それが防げる．例えば，$f$のノルムで$f$を割る (つまり，$f$を正規化する) というアイディアがある．
• 「comparison of Float with Float failed」というエラーは，大きすぎる浮動小数点数が出てきてしまったときに生じる模様．原因は頂点座標が大きくなりすぎることであり，パラメータ設定や上の項目 (力の正規化) および，ノルムの計算の見直しにより防げそうである．ノルムの計算については，資料27ページ目の一番下にある「注意」を参考にするとよいかもしれない．
• Kamada-Kawaiのアルゴリズムにて，私が試したパラメータ$k$の設定は$k=300.0$．
• (10月22日の実験中にした連絡)：プログラムerdos_renyi.rbとbarabasi_albert.rbを改訂したので，コピーをし直して下さい．

参考になる外部ページ

• Rubyリファレンスマニュアル (日本語)
• 逆引きRuby (日本語)
• Ruby/Tkチュートリアル (日本語)
• 逆引きRuby/Tk (日本語)
• Ruby Programming (英語)
• Ruby Programming (at tutorialspoint) (英語)

スケジュール (予定)

1. 10/6 目標の説明，Ruby入門
2. 10/8 力学的モデルに基づく描画アルゴリズムの実装 (1)
3. 10/13 力学的モデルに基づく描画アルゴリズムの実装 (2)
4. 10/15 描画の評価 (1)
5. 10/20 描画の評価 (2)
6. 10/22 描画アルゴリズムの改善
7. 10/27 レポート作成