Pythonでネットワーク分析 ～networkxの使い方～
今回は、ネットワークを使って何かしたいと言うときにオススメなnetworkxの使い方について説明していきます。
例えば、networkxを使うと便利なグラフアルゴリズム(e.g.幅優先探索や深さ優先探索)が簡単に使えてしまうのでオススメです。
また、コミュニティ抽出などのネットワーク分析も気軽に行えます。
※ 実際にtwitterのネットワークを取得して、可視化する記事を書きましたので、カラフルなネットワークを描画したい方はこちらをご覧ください。
※ ニューラルネットワークって難しそう...という方に向けて、ニューラルネットワークの記事を書きましたので、もしよろしければご覧ください。
環境構築
anacondaには初めからは入っていないので、インストールします。
pip install networkx※Google Colobolatoryでは初めから入っているので、インストールせずに使えます。
データを読み込む
今回説明するネットワークは、頂点(ネットワークにおける人を表す)と枝(ネットワークにおける人同士のつながり)に加えて、枝に向きがあり(有向枝)、枝に重み(ネットワークにおける人同士のつながりの強さ)があるネットワークを対象とします。このネットワークのことを重み付き有向グラフとも呼びます。(以下では、ネットワークをグラフと呼びます。)
import pandas as pd
network = pd.read_csv("data.csv")
network.head()| # FromNodeId | ToNodeId | WC | |
|---|---|---|---|
| 0 | 0 | 4 | 0.111111 |
| 1 | 0 | 5 | 0.090909 |
| 2 | 0 | 7 | 0.333333 |
| 3 | 0 | 8 | 0.250000 |
| 4 | 0 | 9 | 0.333333 |
ここでは、このようなデータが与えられているとします。これは、Stanford Large Network Dataset Collectionから取得できるデータに前もって計算した適当な重みを加えたデータです。Stanford Large Network Dataset Collectionではさまざまなソーシャルネットワークデータが参照できます。グラフアルゴリズム関連の論文では、このデータを用いて実験が行われていることもあります。
グラフを作る
networkxではグラフの作り方は多種多様です。ここでは、入力されたデータをnetworkxが受け取れるように変換してから、空の有向グラフを作成し、そのグラフに枝を追加していきます。
# numpyのarray型に変換
network_np = network.values
import networkx as nx
# 空の有向グラフを作成
G = nx.DiGraph()
# 重み付きの枝を加える
G.add_weighted_edges_from(network_np)練習用に小さなグラフを作る
流れは先ほどと同様です。
G_practice = nx.DiGraph()
weighted_edges = [[0,1,0.1],
[0,2,0.2],
[1,3,0.3],
[1,4,0.4],
[2,4,0.5],
[2,0,0.6],
[3,0,0.7],
[3,1,0.8],
[4,3,0.9],
[4,2,1.0]
]
G_practice.add_weighted_edges_from(weighted_edges)正しく作成できているか確認してみます。
import matplotlib.pyplot as plt
# ネットワークを描画できる
nx.draw_networkx(G_practice)
plt.show()
このようにnetworkxではネットワークが簡単に可視化することができる点が魅力です。
networkxの基本的な使い方
以下では、このグラフについて見ていきます。
# 頂点3の情報をみたいとき
G_practice[3]AtlasView({0: {'weight': 0.7}, 1: {'weight': 0.8}})頂点3は頂点0と頂点1にそれぞれ重さ0.7と0.8の有向枝がでていることがわかります。実際に上の図と比較しても合っています。
次にこれを踏まえて、頂点3に向かって枝がでている頂点は以下のように参照できます。(iteratorであるため、list型に変換しています)
list(G_practice.successors(3))[0, 1]上で確認したように頂点0と頂点1であることがわかります。
作成したグラフを変更することもできます。(copy=Trueとすることで元のグラフに干渉しなくなります。)
# グラフの枝の向きを逆にする
G_reverse = nx.reverse(G_practice, copy=True)
nx.draw_networkx(G_reverse)
plt.show()
以下からはグラフの基本的な情報の取得方法を載せています。
# ノード
print(nx.nodes(G_practice))[0, 1, 2, 3, 4]# ノード数
print(nx.number_of_nodes(G_practice))5# グラフの密度
print(nx.density(G_practice))0.5# 各ノードの入次数(ノードid, 入次数)
print(G_practice.in_degree())[(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)]# 各ノードの出次数(ノードid, 出次数)
print(G_practice.out_degree())[(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)]# ノード1の出次数
out_deg = G_practice.out_degree()
print(out_deg[1])2# 指定されたノードから出る枝を列挙
print(G_practice.out_edges(3))[(3, 0), (3, 1)]# 指定されたノードから出る枝を列挙
print(G_practice.out_edges([3]))[(3, 0), (3, 1)]# 指定されたノードから出る枝を列挙(頂点をリストで入力)
print(G_practice.out_edges([3,2]))[(3, 0), (3, 1), (2, 4), (2, 0)]# 指定されたノードに入る枝を列挙
print(G_practice.in_edges(3))[(1, 3), (4, 3)]# 指定されたノードに入る枝を列挙
print(G_practice.in_edges([3]))[(1, 3), (4, 3)]# 指定されたノードから入る枝を列挙(頂点をリストで入力)
print(G_practice.in_edges([3,2]))[(1, 3), (4, 3), (0, 2), (4, 2)]# (0,1)の重みを知りたい場合
print(G_practice[0][1]){'weight': 0.1}# 各ノードの次数(ノードid, 次数)
print(G_practice.degree)[(0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]# ノード3のout-neighbor頂点(頂点3から枝がでている頂点)
print(list(G_practice.successors(3)))[0, 1]# ノード3のin-neighbor頂点(頂点3に枝が入っている頂点)
print(list(G_practice.predecessors(3)))[1, 4]# ノード0からの到達可能ノードまでの最短パス
print(nx.single_source_shortest_path(G_practice, 0)){0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 1, 3], 4: [0, 1, 4]}# ノード0までの到達可能ノードまでの最短パス
print(nx.single_target_shortest_path(G_practice, 0)){0: [0], 2: [2, 0], 3: [3, 0], 4: [4, 2, 0], 1: [1, 3, 0]}pred, dist = nx.dijkstra_predecessor_and_distance(G_practice, 0)
# ノード0から各ノードへの最短経路における手前の頂点
# 辿ることで最短経路がわかる
print(sorted(pred.items()))
# ノード0から各頂点までの距離
print(sorted(dist.items()))[(0, []), (1, [0]), (2, [0]), (3, [1]), (4, [1])]
[(0, 0), (1, 0.1), (2, 0.2), (3, 0.4), (4, 0.5)]# ノード0からノード4までの最短経路
print(nx.dijkstra_path(G_practice,0,4))[0, 1, 4]# 任意のノード間についてダイクストラで計算
len_path = dict(nx.all_pairs_dijkstra(G_practice))
# ノード3から各ノードへの最短距離
print(len_path[3][0])
# ノード3から各ノードへの最短経路
print(len_path[3][1]){3: 0, 0: 0.7, 1: 0.7999999999999999, 2: 0.8999999999999999, 4: 1.2}
{3: [3], 0: [3, 0], 1: [3, 0, 1], 2: [3, 0, 2], 4: [3, 0, 1, 4]}# 任意のノード間について最短距離が1以下の経路をダイクストラで計算
len_path = dict(nx.all_pairs_dijkstra(G_practice, cutoff=1))
# 上と比較すると、ノード3から4への経路が消えている
# ノード3から各ノードへの最短距離
print(len_path[3][0])
# ノード3から各ノードへの最短経路
print(len_path[3][1]){3: 0, 0: 0.7, 1: 0.7999999999999999, 2: 0.8999999999999999}
{3: [3], 0: [3, 0], 1: [3, 0, 1], 2: [3, 0, 2]}cutoffを指定することで、指定した距離で探索を打ち切ってくれるため、最短距離での閾値が設定されている場合は有効です。
%timeit len_path = dict(nx.all_pairs_dijkstra(G_practice))
%timeit len_path = dict(nx.all_pairs_dijkstra(G_practice, cutoff=1))74.1 µs ± 5.49 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
60.9 µs ± 3.92 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)# 各頂点から頂点4までの最短経路がわかる
for n, (dist, path) in nx.all_pairs_dijkstra(G_practice):
print(path.get(4))[0, 1, 4]
[1, 4]
[2, 4]
[3, 0, 1, 4]
[4]# グラフが木構造であるかどうかを判定する
print(nx.is_tree(G_practice))Falseまとめ
今回は、networkxでグラフを作成して、基本情報を取得しました。また、ダイクストラ法と呼ばれる最短経路を求めるアルゴリズムを使いました。networkxでは他にもさまざまなグラフアルゴリズムを利用することができます。気になる方はこちらをご覧ください。
最後に、networkxは気軽にネットワーク分析や可視化をするには優れたライブラリではありますが、大規模なグラフを扱うには処理が重く、計算にも描画にも時間がかかってしまうと言う欠点があります。大規模なグラフに関しては、pythonではgraph-toolsが速いとされています。しかし、インストールが困難であることや日本語のリファレンスがないことが挙げられます。
書籍
ネットワークについて知りたい方は以下をおすすめします。
