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

python network

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

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

見たままですね．ちなみに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です．



(データはこちら．左から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としてシミュレーションをしてみました．コードは以下のようになります．


実行結果



最初の図は各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


(2) p = 0.05
必要ステップ数: 9
平均経路長: 5.318636636636636
クラスタリング係数: 0.5792653735153729


(3) p = 1
必要ステップ数: 5
平均経路長: 3.2708968968968968
クラスタリング係数: 0.009309777477424539



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


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


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