NetworkXによるモデルからのネットワーク生成

# 動画解説
この記事で紹介するネットワークモデルについて[私のチャンネル](https://www.youtube.com/channel/UC0UnEjW_QUMHqjvQXYJ3WhQ)の以下の動画で，それぞれさらに詳しく解説していますので，よろしければ併せてご覧ください．もし今後とも役に立ちそうであればチャンネル登録もよろしくお願いします．

- Erdős–Rényiのランダムグラフ（作成したプログラムの[Jupyterファイル](https://ux.getuploader.com/kenkyuprogram/download/16)） 
<iframe width=560" height="315" src="https://www.youtube.com/embed/GgCn92_vb40" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

- Watts–Strogatzのスモールワールドネットワーク（作成したプログラムの[Jupyterファイル](https://ux.getuploader.com/kenkyuprogram/download/12)）
<iframe width="560" height="315" src="https://www.youtube.com/embed/Hp4HsoeHA2g" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

- Barabási-Albertのスケールフリーネットワーク（作成したプログラムの[Jupyterファイル](https://ux.getuploader.com/kenkyuprogram/download/15)）
<iframe width="560" height="315" src="https://www.youtube.com/embed/uFISKHqGQAU" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

# モデルからのネットワーク生成
[前回の記事](https://qiita.com/igenki/items/044fd4c06b643a3f781a)ではNetworkXによる**ネットワークの作成と可視化**について解説しました．前回はネットワークを一から作ってみましたが，NetworkXには**ネットワークモデルを1行で生成できる様々な組み込み関数**が用意されています．今回はネットワークモデルとしてよく知られている**Erdős–Rényiのランダムグラフ，Watts–Strogatzのスモールワールドネットワーク，Barabási-Albertのスケールフリーネットワーク**の3つを組み込み関数から生成する方法を紹介したいと思います．

## Erdős–Rényiのランダムグラフ
最初はランダムグラフの生成と可視化です．ランダムグラフにもいろいろ種類がありますが，ここでは[Erdős–Rényiのランダムグラフ](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model)を作成します．このネットワークは$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)$のランダムグラフを生成してくれます．では早速このグラフを生成して可視化してみましょう．実際のコードは以下のようになります．

```python
%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)
```

これを実行するとネットワークの基本情報が出力されるとともに，以下のようなグラフが可視化されます．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/663791/4363bac6-b77f-3505-741e-597a37ce2a56.png)

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`を指定して，ノードを円環状に配置しています．

[^1]: リンクを張る確率$p$が小さい値の場合，ネットワークが分断される（非連結になる）ことが多々あります．この場合，$L$は計算できなくなるので，エラーが出ます．

## Watts–Strogatzのスモールワールドネットワーク
次は，[Watts–Strogatzのスモールワールドネットワーク](https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model)を生成します．このネットワークは$G(n,k,p)$で規定されます．$n$はノード数で，$k$は次数，$p$はリンクを張り替える確率です．ノード$n$個を円環状に配置します．各ノードから$k/2$個まで右隣に，残り$k/2$個まで左隣にリンクを張っていき，規則的なネットワークを生成します．その後，各リンクに対して確率$p$でランダムにリンクを張り替える（片方の端点を切り離し，ランダムに選んだノードに接続する）とスモールワールドネットワークが生成されます．Watts–Strogatzのスモールワールドネットワークは，クラスタ係数$C$が大きいままで，平均距離$L$が小さいという特徴があります．これは元々規則的なグラフがベースとなっていて，いくつかのリンクがランダムに再接続されることによってショートカットができるためです．では，このグラフを生成して可視化してみましょう．実際のコードと実行結果は以下のようになります．

```python
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)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/663791/9aaf7a07-11b9-0aa3-72be-2ace0ed47d7a.png)

まずは，$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のスケールフリーネットワーク](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model)を生成します．このネットワークは$G(n, m)$で規定されます．ネットワークは$m_0$個の連結した状態からスタートします[^2]．$m$本のリンクを持つノードを1つずつネットワークに追加します．$m$本の新しいリンクは，それぞれ，既存のノードに対して，既存のノードの次数に比例した確率で接続します．したがって，次数が大きいノードがリンクを集めやすくなります．これを優先的選択と言います．ノードの追加をノード数が$n$になるまで繰り返します．こうしてできるネットワークがスケールフリーネットワークです．Barabási-Albertのスケールフリーネットワークは，次数分布がべき分布になるという特徴があります．では，このグラフを生成して可視化してみましょう．実際のコードと実行結果は以下のようになります．

[^2]: NetworkX の`nx.barabasi albert graph(n, m)`関数では$m_0 =m$で固定されていますが，$m \leq m_0$であれば異なっていても構いません．

```python
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)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/663791/4f423056-3a55-e80b-74ff-6daa8f049790.png)

$n$と$m$のパラメータをそれぞれ，$n=100,m=2$で与えます．スケールフリーネットワークの生成は，`nx.barabasi albert graph(n, m)` の1行でできます．このネットワークをBA という名前で保存しています．あとは上記の2つのネットワークと同じです．

# まとめ
ネットワーク分析ができるPythonパッケージのNetworkXを用いて，今回は，組み込み関数から代表的なネットワークモデルを作成してみました．このQiitaの記事は私が以前に書いた文献[1]の一部を加筆修正して執筆しました．ネットワークの用語や理論に関しては，文献[2] を参考にさせていただきました．NetworkXのプログラミングについては文献[3]を参考にさせていただきました．
[私のYouTubeチャンネル](https://www.youtube.com/channel/UC0UnEjW_QUMHqjvQXYJ3WhQ)では**研究で使うPython**シリーズを公開していますので，そちらも是非ご確認ください．

### 参考文献
1. 一ノ瀬元喜, 宮川大樹, 【第3回数理生物研究×計算機】ネットワーク生成とネットワーク上のダイナミクス, 日本数理生物学会ニュースレター 93, 16-23, 2021.
2. 増田直紀, 今野紀雄. 複雑ネットワーク：基礎から応用まで. 近代科学社, 2010.
3. 村田剛志. Pythonで学ぶネットワーク分析：ColaboratoryとNetworkXを使った実践入門. オーム社, 2019.