動画解説
この記事で紹介するネットワークモデルについて私のチャンネルの以下の動画で，それぞれさらに詳しく解説していますので，よろしければ併せてご覧ください．もし今後とも役に立ちそうであればチャンネル登録もよろしくお願いします．
- Erdős–Rényiのランダムグラフ（作成したプログラムのJupyterファイル）
- Watts–Strogatzのスモールワールドネットワーク（作成したプログラムのJupyterファイル）
- Barabási-Albertのスケールフリーネットワーク（作成したプログラムのJupyterファイル）
モデルからのネットワーク生成
前回の記事ではNetworkXによるネットワークの作成と可視化について解説しました．前回はネットワークを一から作ってみましたが，NetworkXにはネットワークモデルを1行で生成できる様々な組み込み関数が用意されています．今回はネットワークモデルとしてよく知られているErdős–Rényiのランダムグラフ，Watts–Strogatzのスモールワールドネットワーク，Barabási-Albertのスケールフリーネットワークの3つを組み込み関数から生成する方法を紹介したいと思います．
Erdős–Rényiのランダムグラフ
最初はランダムグラフの生成と可視化です．ランダムグラフにもいろいろ種類がありますが，ここではErdős–Rényiのランダムグラフを作成します．このネットワークは$G(n,p)$で規定されます．$n$はノード数で，$p$はノードの各ペア（ノード2つで1ペア）にリンクが張られる確率です．$_n C _2$ 通りのペアの数がありますが，それぞれのペアに対して確率$p$でリンクを張ります．$n=10, p=0.1$だとすると全部で45通りのペアがありますが，それぞれのペアに対して確率0.1でリンクを張ります．Erdős–Rényiのランダムグラフを生成するNetworkXの組み込み関数はerdos_renyi_graph()でこの関数に$n$と$p$を渡すことで$G(n,p)$のランダムグラフを生成してくれます．では早速このグラフを生成して可視化してみましょう．実際のコードは以下のようになります．
%matplotlib inline
import networkx as nx
n = 100 # ノード数
p = 0.05 # リンク接続確率
print('ER network')
ER = nx.erdos_renyi_graph(n, p)
print(nx.info(ER))
print('L=', nx.average_shortest_path_length(ER))
print('C=', nx.average_clustering(ER))
pos = nx.circular_layout(ER)
nx.draw(ER, pos)
これを実行するとネットワークの基本情報が出力されるとともに，以下のようなグラフが可視化されます．
1行目の%matplotlib inlineはJupyter上で画像を表示するためのものです．import networkx as nxでNetworkXをインポートしてnxという名前で使えるようにしています．今回ランダムグラフの$n$と$p$には，それぞれ$n=100$, $p=0.05$を与えます．ER = nx.erdos_renyi_graph(n, p)でネットワーク（のオブジェクト）を生成してERという名前で保存しています．nx.info(ER)で生成されたERネットワークの基本的な情報であるノード数，リンク数，平均次数を出力しています．$n=100$なのでノード数は100でいつも固定ですが，リンクを張るかどうかは確率$p$で決まるので，リンク数と平均次数は実行のたびに結果が変わります．次数とは，ノードごとの量で，ノードにつながっているリンクの数です．これを全てのノードに渡って平均をとったもの平均が平均次数です．nx.average shortest path length(ER)でこのネットワークの平均距離$L$を求めることができます．距離は，2つのノード（ノードのペア）の間の最短経路の長さで定義されます．全てのペアに渡る平均をとったものが平均距離$L$となります．nx.average clustering(ER)によってこのネットワークのクラスタ係数$C$を求めています．クラスタ係数はノードごとの量で，ノード$i$のクラスタ係数$C_i$はノード$i$とつながっている2つのノード同士がつながっている割合です．$C_i$を全てのノードに渡って平均をとったものが$C$となります．最後にnx.draw(ER)でこのネットワークを描画しています1．ここでは見やすいように，posにcircular layoutを指定して，ノードを円環状に配置しています．
Watts–Strogatzのスモールワールドネットワーク
次は，Watts–Strogatzのスモールワールドネットワークを生成します．このネットワークは$G(n,k,p)$で規定されます．$n$はノード数で，$k$は次数，$p$はリンクを張り替える確率です．ノード$n$個を円環状に配置します．各ノードから$k/2$個まで右隣に，残り$k/2$個まで左隣にリンクを張っていき，規則的なネットワークを生成します．その後，各リンクに対して確率$p$でランダムにリンクを張り替える（片方の端点を切り離し，ランダムに選んだノードに接続する）とスモールワールドネットワークが生成されます．Watts–Strogatzのスモールワールドネットワークは，クラスタ係数$C$が大きいままで，平均距離$L$が小さいという特徴があります．これは元々規則的なグラフがベースとなっていて，いくつかのリンクがランダムに再接続されることによってショートカットができるためです．では，このグラフを生成して可視化してみましょう．実際のコードと実行結果は以下のようになります．
n = 100 # ノード数
k = 4 # 次数
p = 0.1 # リンク張り替え確率
print('WS network')
WS = nx.watts_strogatz_graph(n, k, p)
print(nx.info(WS))
print('L=', nx.average_shortest_path_length(WS))
print('C=', nx.average_clustering(WS))
pos = nx.circular_layout(WS)
nx.draw(WS, pos)
まずは，$n, k, p$のパラメータをそれぞれ，$n=100, k=4, p=0.1$と与えます．スモールワールドネットワークの生成は，nx.watts strogatz graph(n, k, p)の1 行でできます．このネットワークをWSという名前で保存しています．基本情報の出力と平均距離$L$，クラスタ係数$C$もランダムネットワークの場合と同様に出力させています．最後にnx.draw(WS)でこのネットワークを描画しています．
Barabási-Albertのスケールフリーネットワーク
最後に，Barabási-Albertのスケールフリーネットワークを生成します．このネットワークは$G(n, m)$で規定されます．ネットワークは$m_0$個の連結した状態からスタートします2．$m$本のリンクを持つノードを1つずつネットワークに追加します．$m$本の新しいリンクは，それぞれ，既存のノードに対して，既存のノードの次数に比例した確率で接続します．したがって，次数が大きいノードがリンクを集めやすくなります．これを優先的選択と言います．ノードの追加をノード数が$n$になるまで繰り返します．こうしてできるネットワークがスケールフリーネットワークです．Barabási-Albertのスケールフリーネットワークは，次数分布がべき分布になるという特徴があります．では，このグラフを生成して可視化してみましょう．実際のコードと実行結果は以下のようになります．
n = 100 # ノード数
m = 2 # 新規ノード接続リンク数
print('BA network')
BA = nx.barabasi_albert_graph(n, m)
print(nx.info(BA))
print('L=', nx.average_shortest_path_length(BA))
print('C=', nx.average_clustering(BA))
pos = nx.circular_layout(BA)
nx.draw(BA, pos)
$n$と$m$のパラメータをそれぞれ，$n=100,m=2$で与えます．スケールフリーネットワークの生成は，nx.barabasi albert graph(n, m) の1行でできます．このネットワークをBA という名前で保存しています．あとは上記の2つのネットワークと同じです．
まとめ
ネットワーク分析ができるPythonパッケージのNetworkXを用いて，今回は，組み込み関数から代表的なネットワークモデルを作成してみました．このQiitaの記事は私が以前に書いた文献[1]の一部を加筆修正して執筆しました．ネットワークの用語や理論に関しては，文献[2] を参考にさせていただきました．NetworkXのプログラミングについては文献[3]を参考にさせていただきました．
私のYouTubeチャンネルでは研究で使うPythonシリーズを公開していますので，そちらも是非ご確認ください．
参考文献
- 一ノ瀬元喜, 宮川大樹, 【第3回数理生物研究×計算機】ネットワーク生成とネットワーク上のダイナミクス, 日本数理生物学会ニュースレター 93, 16-23, 2021.
- 増田直紀, 今野紀雄. 複雑ネットワーク：基礎から応用まで. 近代科学社, 2010.
- 村田剛志. Pythonで学ぶネットワーク分析：ColaboratoryとNetworkXを使った実践入門. オーム社, 2019.