ネットワーク可視化のアルゴリズム
情報数理工学実験第二A・B，コンピュータサイエンス実験第二A・B
電気通信大学情報理工学部情報・通信工学科
2015年度後学期
月曜3，4限と水曜3，4限
第2ラウンド
岡本 吉央
概要
ネットワーク可視化のための基本的なアルゴリズムを実装し，アルゴリズム設計と評価の方法論，実装上の注意点を主体的に学ぶ．その中で，ネットワーク，最適化，数値計算，計算幾何学など，様々な分野が有機的に関連している様子を体感する．
ネットワーク可視化，グラフ描画，力学的モデル，最適化，計算幾何学
イメージ図
レポート提出締切
- 締切：12月10日 (木) 13:00
- 提出方法：電子媒体 (メール) と紙媒体 (レポートボックス)
- メール：プログラムのソース，適当に圧縮して送付すること (圧縮コマンドはgzip, bzip2, tarなどがある)
- 紙に印刷したもの：普通のレポート
このレポートの中でプログラムのソースなどを参照する場合は，ファイル名と行番号を明示すること
- 提出先
- 再提出の場合は，メールで12月17日までに個別連絡．
テキストの訂正
- 1ページ目, 下から10行目：エリア2 → エリア1
- 38ページ目，式(43)と(44)：右辺を，その絶対値に修正．
- 43ページ目，Step 4-1-2-2：$c_{i,j}$ → $\sigma_{i,j}$
補足
- Rubyにて，文字列strを整数に変えるには「str.to_i」として，文字列strを浮動小数点数に変えるには「str.to_f」とする．
例："12345".to_i => 12345, "12.345".to_f => 12.345
- CEDにてスクリーンショットを取るには，「Fn」を押しながら「i」を押す．そのとき出てくるウィンドウに従って保存する．
- 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$．
参考になる外部ページ
CEDに標準インストールされているRubyのバージョンは2.1.0であることに注意．
スケジュール (予定)
- 11/4 目標の説明，Ruby入門
- 11/9 力学的モデルに基づく描画アルゴリズムの実装 (1)
- 11/11 力学的モデルに基づく描画アルゴリズムの実装 (2)
- 11/16 描画の評価 (1)
- 11/18 描画の評価 (2)
- 11/23 祝日のため休み
- 11/25 描画アルゴリズムの改善
- 11/30 レポート作成
[Teaching Top]
[Top]
okamotoy@uec.ac.jp