大規模グラフの可視化の手法・ソフトウェア

面白そうなので気が向いた時に調べる．随時情報追加予定．

基礎

• http://en.wikipedia.org/wiki/Graph_drawing これを読むぞ！
• http://www.csse.monash.edu.au/hons/se-projects/2006/Kieran.Simpson/output/html/node2.html コレも気になる！

なんかのソフトウェアパッケージの論文より引用 http://www.necsi.edu/events/iccs6/papers/c1602a3c126ba822d0bc4293371c.pdf

Graph layouts The following layout generators are part of igraph:  simple
circle and sphere layouts, random layouts  Fruchterman-Reingold layout, 2D
and 3D [8]  Kamada-Kawai layout, 2D and 3D [9]  spring embedder layout 
LGL layout generator for large graphs [15]  Grid-based Fruchterman-Reingold
layout for large graphs  Reingold-Tilford layout [14] for trees.

このへんのキーワードも調べるか

手法のカテゴリ

• force-based layout systems
  • エネルギーを最小化するものと，普通に直接シミュレーションするものがある
  • http://www.csse.monash.edu.au/hons/se-projects/2006/Kieran.Simpson/output/html/node8.html
  • http://www.csse.monash.edu.au/hons/se-projects/2006/Kieran.Simpson/output/html/node9.html
• Spectral layout methods
  • 固有ベクトル
• Orthogonal layout methods
  • あんま関係なさそう
• Tree layout algorithms
  • ツリー
• Layered graph drawing methods (often called Sugiyama-style drawing)
  • best suited for directed acyclic graphs or graphs that are nearly acyclic
• Circular layout methods
  • graphviz の circo やな

Fruchterman-Reingold layout

• 基本的にはバネ
• http://wiki.gephi.org/index.php/Fruchterman-Reingold

T.M.J. Fruchterman and E.M. Reingold introduced a "global temperature" that controls the step width of node movements and the algorithm's termination. The step width is proportional to the temperature, so if the temperature is hot, the nodes move faster (i.e, a larger distance in each single step). This temperature is the same for all nodes, and cools down at each iteration. Once the nodes stop moving, the system terminates.

Kamada-Kawai Model

• http://www.csse.monash.edu.au/hons/se-projects/2006/Kieran.Simpson/output/html/node10.html
• やっぱ基本的にはバネ
• 二頂点間の最短距離を用いて，空間での距離がそれに近くなるようにする

新しそうな気になるもの

Large Graph Layout

• サイト http://lgl.sourceforge.net/
• DL http://sourceforge.net/projects/lgl/
• 論文 http://www.ncbi.nlm.nih.gov/pubmed/15184029?dopt=Abstract
• 論文 http://www.marcottelab.org/paper-pdfs/jmb-lgl.pdf
• 結果の例 http://www.opte.org/maps/

MST を使って順に頂点を増やしながら配置を行う．バネモデルだが，バケット法を使って計算量を減らしている．

SFDP

• ページ (w/論文へのリンク) http://www2.research.att.com/~yifanhu/SOFTWARE/SFDP/index.html
• 例（複雑ネットワーク） http://www.cise.ufl.edu/research/sparse/matrices/SNAP/
• 例（最適化問題？） http://www2.research.att.com/~yifanhu/GALLERY/GRAPHS/index1.html

web-Google とかを可視化したとき，岩田が作ってた画像で出てきたような，大量のクリークみたいなのが全く写っていない．全頂点描画するとこうなってしまうものなんだろうか．

@tatsushi_do_ob さんのやつ

• ページ http://www.kecl.ntt.co.jp/as/members/tatsushi/graphdrawing.html
• 論文 https://www.waset.org/journals/ijece/v2/v2-10-97.pdf
• LGL より凄いらしい！

やっぱこういうの研究するのは物理系の人が強いんかなぁ．物理っぽいシミュレーションとかもろに関係しているわけだし．

その他

引っかかった論文

• http://jgaa.info/accepted/2007/HachulJuenger2007.11.2.pdf
  • largeとか言いながら<1M edgesはちょっと……
• ひたすらグラフを可視化するサイト http://griffsgraphs.com/