Hatena::ブログ(Diary)

mfumiの日記

2014-02-13

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

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


f:id:mFumi:20140213192203p:image:w360


f:id:mFumi:20140213192202p:image:w360


f:id:mFumi:20140213192201p:image:w360


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


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

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




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



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


f:id:mFumi:20140213192405p:image:w360


図に示したように,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回の変化を小さくしています).

f:id:mFumi:20140213192411g:image

before

f:id:mFumi:20140213192409p:image


after

f:id:mFumi:20140213192410p:image

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

f:id:mFumi:20140213192412p:image


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


別の例

f:id:mFumi:20140213192922g:image


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

2014-02-12

NetworkXによるスモールワールドネットワークの生成

NetworkXpython製の複雑ネットワークのためのライブラリです.NetworkXを使うと,お手軽にグラフ構造が作成できます.平均経路長(2点のノード間の平均距離)やクラスタリング係数(隣接ノード同士が接続している割合)といったネットワークの特徴量を求める関数が用意されているのは勿論のこと,経路探索や,さらにはPageRankHITSといったものも簡単に計算できます.また,matplotlibを使うことで描画もできます.

インストール

$ pip install networkx matplotlib

でできます(ちなみにMac OS 10.9ではln -s /usr/local/opt/freetype/include/freetype2 /usr/local/include/freetypeしないと駄目でした).

NetworkXのサンプルは以下のようになります(以下python3です).

#!/usr/bin/env python
import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edge(1,2)
G.add_edge(2,3)
nx.draw(G)
plt.savefig("a.png")

これで以下のグラフが生成されます.

f:id:mFumi:20140212222847p:image

見たままですね.ちなみにadd_node()では基本的にどんなオブジェクトでも追加できます.今回はこのNetworkXを使ってスモールワールドネットワークの検証をしてみることにしました.


スモールワールドネットワークとは複雑系ネットワークに分類されるネットワークの一種で,簡単にいってしまうと

(1)全体のノード数に対して各ノードが持つリンク数(辺の数)が小さいが,平均経路長は短い,

(2)クラスタリング係数が高い

という性質を持つネットワークです.これは現実世界のネットワークがよく持つ性質です.例えば,人間関係ネットワークを考えてみると,全人口に対して一人の人間が持つリンク数(知人数)は小さいです.また,ある人の友人同士が友人である確率はそれ以外の場合に比べると高い(クラスタリング係数は高い)と考えられます.平均経路長が短いというのは直感には合わないかもしれませんが,有名なミルグラムの実験の結果で示されるように,どんな人でも友人を辿っていけば6人以下でほぼ到達できることが分かっています.

1998年にWatssらがこのスモールワールドネットワークを定式化し,生成する方法を発表しました(論文はこれ).この論文の登場によって一気に複雑系ネットワークの研究が進んだそうで,引用数2万overとよく分からないことになってます.

この論文でのスモールワールドネットワーク生成方法は発表者の氏名をとってWatts & Strogtzモデル(WSモデル)と呼ばれます.WSモデルの生成方法は以下のようになります.


1. グラフ内にN個のノードを追加する(それぞれ1~Nと番号をつける)

2. 各ノードを隣接k個のノードと接続する (例えばk=1ならノード1はノード2とノードN と接続)

3. グラフ内の各辺それぞれについて,確率pでリンクを適当なノードに繋ぎ変える(重複は禁止)


ここでp=0の場合は何も繋ぎ変えが起こらず,この場合平均経路長は長く,クラスタリング係数は大きくなります.またp=1の場合はいわゆるランダムネットワークが生成され,平均経路長が短く,クラスタリング係数は小さくなります.pが中間ぐらいのとき,先ほどの言った平均経路長が短くクラスタリング係数が高いというスモールワールドネットワークが生成されます.

NetworkXにはこのWSモデルでネットワークを生成する関数が当然ながら用意されているのですが,まぁ折角なので自分で論文の方法に忠実に作ってみました.



make_small_world_netork()がWSモデルによるスモールワールドネットワーク生成関数です.ただ作るだけでは意味がないので,論文と同じように確率pを変化させ平均経路長L(p)とクラスタリング係数C(p)のp=0に対する比のグラフを生成してみます.ノード数と各ノード辺の数はそれぞれ1000と10です.


f:id:mFumi:20140212222853p:image


(データはこちら.左からp,L(p)/L0,C(p)/C0です)

論文のFigure2と同じような結果が得られました(ならないと困りますが..).x軸は対数スケールです.このグラフから(1)平均経路長はp=0.01でも十分小さい(p=1のランダムネットワークの平均経路長に近い),(2)一方pが1付近でなければクラスタリング係数はランダムネットワークよりも十分大きい(p=0のクラスタリング係数に近い),ということが分かります.これがスモールワールドネットワークの持つ性質です.


さて,論文の後半ではこのスモールワールドネットワークを使って簡単な病気の伝染のシミュレーションをおこなっているので,それもやってみることにします.シミュレーションの流れは以下のようになります.


1. スモールワールドネットワークを生成する.(各ノードが人を表す)

2. ノード0 が伝染病に感染しているとする(初期条件)

3. 確率rで感染しているノードの隣接ノード感染する

4. 感染したノードは一定ステップ後に取り除かれる(死亡)

5. 全てのノード感染 or 感染しているノードが存在しなくなったらシミュレーションを終了


論文にはノードの大きさや辺の数が書いていないようなので,先ほどと同じノード数1000,各ノードのリンク数10,また感染してから死亡するまでの時間を2としてシミュレーションをしてみました.コードは以下のようになります.


実行結果

f:id:mFumi:20140212222851p:image


f:id:mFumi:20140212222852p:image


最初の図は各pに対してrを変化させ,半分以上のノード感染する確率r_halfをグラフにしたものです.また,2番目の図はr=1(常に隣接ノード感染)と固定した場合に全てのノード感染するまでにかかる時間T(p)をp=0のときの値T0で割ったグラフです(データはこちら.左からp,r_half,T(p)/T0,L(p)/L0です).x軸は先ほど同様に対数スケールです.これらの図は論文のFigure3に相当します.この図から(1)r_halfはpが小さいところで急激に減少する(p > 0.1 ではあまり変化がない),(2)T(p)/T(0)のグラフはL(p)/L(0)のグラフに近く,つまりpが0.01程度でも急速に感染が進む,ということが分かります.


また,r=1のときにp=0,0.05,1のそれぞれについてどのように伝染していくか図にしてみると以下のようになります(ソース)

(1) p = 0

必要ステップ数: 101

平均経路長: 50.450450450450454

クラスタリング係数: 0.6666666666666636

f:id:mFumi:20140212222849g:image


(2) p = 0.05

必要ステップ数: 9

平均経路長: 5.318636636636636

クラスタリング係数: 0.5792653735153729

f:id:mFumi:20140212222850g:image


(3) p = 1

必要ステップ数: 5

平均経路長: 3.2708968968968968

クラスタリング係数: 0.009309777477424539

f:id:mFumi:20140212222848g:image



このようにp=0.05でも十分平均経路長は短く,あっという間に伝染していく様子が観察できます.平均経路長が短くなる理由は,辺の繋ぎ変えをおこなうことで遠くのノード同士を繋ぐショートカットが生成されるからです.


さて,このような感じでとても簡単な方法でスモールワールドネットワークが生成できて,現実世界のネットワークをよく近似しますが,実は現実世界のネットワークはスモールワールドネットワークが持っていない重要なある性質を持っています.それはスケールフリー性です.スケールフリー性を持つネットワークは次数分布(次数はあるノードにおける辺の数のこと)がベキ分布に従い,高次元のノード数が少なく,低次元のノードが多くなります(WSモデルでは全てのノードの辺の数は等しいです).このスケールフリー性を持つネットワークスケールフリーネットワーク)を生成する方法がWSモデルの1年後の1999年にBarabasiらによって発表されました.例えば,Twitterなんかではごく一部のユーザのみが膨大なフォロワー数を持っていますね.勿論NetworkXにはスケールフリーネットワークを生成する関数が用意されています.


スケールフリーネットッワークについては次回?