グラフ(ネットワーク)を奇麗に描画するアルゴリズム

network python

グラフはノードと辺の集合から構成されているだけなので，その描画方法は任意です．例として，以下の3つのグラフはどれも同じです．





グラフをどうやって奇麗に描画するかという研究は昔からおこなわれていて，そのうちの一つに力学モデルがあります(Wikipedia)．このモデルではノード間にある力が作用すると考えてそれが安定するような場所を探します．簡単な例ではノードを電荷だと仮定してそれぞれに働くクーロン力を計算し，それをもとにノード位置の修正をおこないます．


力学モデルのアルゴリズムで代表的なものにFruchterman-Reingold アルゴリズムがあります．このアルゴリズムは多くのグラフを扱うライブラリでサポートされているようです．

このアルゴリズムの考え方はシンプルで，ノードに影響する力が2つあります．一つは自分以外の全てのノードからの斥力，もう一つが隣接ノードからの引力です．斥力f_rと引力f_aは以下の式で定義されます．




ここで k は以下の式で定義されます．



areaは描画領域の面積(横幅W,縦幅Lだとするとarea = W*L)，|V|は頂点数，cはある定数です．f_rとf_aの関係を図にすると以下のようになります(k=10の場合)．



図に示したように，d=kのときf_a + f_rは0となります．アルゴリズムではdをノード間の距離だとして，それぞれのノードがなるべくkだけ離れているような場所を探します．つまり，kはノード間の理想距離として定義されています．もしあるノード間の距離がkよりも大きくはずれていたらそれを修正するように力が働きます．
斥力と引力の式は実験的に求めたもので，どちらもフックの法則に似ています．論文では斥力・引力の候補として




を考えてみたものの，この場合だと極所解に陥ることが多かったということが書かれています．


また，もう一つアルゴリズムにおける重要な考えとして，温度パラメータtがあります．この温度パラメータは，変位の最大値を決定します．つまり，引力と斥力の影響を考慮してノードを動かすわけですが，あまり大きく動いてしまっても困るので，t以下に制限するわけです．いまいちこの温度パラメータに関しては論文に載っていないような気がしますが，一つの例としてはtの初期値を病が領域の横幅の10分の1とし，それを1回の繰り返しごとに徐々に減少させていく方法があります．


実際のアルゴリズムの処理の流れは以下のようになります．


1. 各頂点間に働く引力/斥力を計算
2. 1. で計算した値をもとに頂点を動かす．ただし，このとき枠外に出ないようにする．また，動かす変位の大きさは温度パラメータt以下とする．
3. 温度パラメータを下げる
4. 以上の処理をある一定回数繰り返す．


基本的な計算量はO(|V|^2 + |E|)になります．計算を高速化する手法として論文では領域をいくつかに分割し，ある領域内にいるノードはその領域内の他のノードからのみ力を受けると仮定して計算する方法が書かれています(この辺りちゃんと読んでない..)．計算の終了条件がただのループのみなので，一定時間での計算が保障されています．斥力は自分以外の全てのノードから，引力は自分が繋がっているノードからのみ受けるという点も割とポイントだと思います．


さて，このアルゴリズムを実際にpythonで実装をしてみます．グラフ自体の表現にはNetworkXを使います (なお，NetworkXではspring_layoutがFruchterman-Reingold アルゴリズムの実装です．デフォルトでNetowkXで描画するとこのアルゴリズムが使用されます)．論文に擬似コードが載っていますので，そのまま素直に実装します．



fruchterman_reingold()が実際のアルゴリズム部分です．この実装では領域は中心(0.5,0.5)，半径0.5の円としています(領域を四角にしてしまうとグラフが四角くなりやすくなるため)．
実際にグラフの構造が変化する流れは以下のようになります(この例ではわざとtを小さくとって1回の変化を小さくしています)．

before


after

NetworkXにもともとあるfruchterman-reingoldを使って描画すると以下のようになります．


こんなものですかね．NetworkXの方が若干良さそうな感じがしなくもないですが．


別の例


ということで以上のような感じで比較的シンプルにグラフを奇麗に描画することができます．ちなみに上のpythonの例ではほぼ擬似コードそのままで最適化もなにもしていないしそもそも計算方法自体が最も基本的なものなので遅いです．まぁ参考ということで．NetworkXなら素直にspring_layout使いましょう．