pythonによるネットワーク分析のメモ書きとなります。
networkxを使用します。
内容・コードがまとまっていないので、詳細については参考書の参照をお願いします。
機会があればしっかり勉強していこうと思います。
幅優先探索と深さ優先探索
ネットワーク$G=(V,E)$の2頂点$v_s$と$v_t$が与えられて、$v_s$から$v_t$への経路を探索することを考える。
幅優先探索(BFS)は、$v_s$に隣接する距離1の頂点をすべて探し、次に距離2のすべての頂点、さらに距離3のすべての頂点という順で探索していく手法である。
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
import networkx as nx
data = pd.read_csv('anketo.csv', encoding='shift-jis')
data.head()
| Term1 | Term2 | 度数 | |
|---|---|---|---|
| 0 | 学費を | 低く/安く | 20 |
| 1 | 単位を | 取り | 4 |
| 2 | もっと | 取り | 3 |
| 3 | 自動車通学の | 許可。 | 3 |
| 4 | 学食を | 安く。 | 3 |
# Graphオブジェクトの作成
G = nx.Graph()
# nodeデータの追加
G.add_nodes_from(np.unique([data.Term1]+[data.Term2]))
# edgeデータの追加
G.add_weighted_edges_from([(data.loc[i, 'Term1'], data.loc[i, 'Term2'], data.loc[i, '度数']) for i in range(len(data))])
pos = nx.spring_layout(G)
# ネットワークの可視化
nx.draw(G, with_labels = False, node_size = 10, pos=pos, node_color='lightblue', width=0.2)
plt.show()
print("BFS", list(nx.bfs_edges(G, source='学費を'))[:10])
d1 = list(nx.bfs_edges(G, source='学費を', depth_limit=1))
print('depth 1:', d1[-10:])
d2 = list(nx.bfs_edges(G, source='学費を', depth_limit=2))
print('depth 2:', d2[-10:])
d3 = list(nx.bfs_edges(G, source='学費を', depth_limit=3))
print('depth 3:', d3[-10:])
d4 = list(nx.bfs_edges(G, source='学費を', depth_limit=4))
print('depth 4:', d4[-10:])
d5 = list(nx.bfs_edges(G, source='学費を', depth_limit=5))
print('depth 5:', d5[-10:])
BFS [('学費を', '低く/安く'), ('学費を', '下げて下さい。'), ('学費を', '払っているのに、'), ('学費を', '高い'), ('下げて下さい。', 'もう少し'), ('払っているのに、', 'つまんないから'), ('高い', 'お金が'), ('高い', '割に'), ('もう少し', '取り'), ('もう少し', '安く。')]
depth 1: [('学費を', '低く/安く'), ('学費を', '下げて下さい。'), ('学費を', '払っているのに、'), ('学費を', '高い')]
depth 2: [('学費を', '低く/安く'), ('学費を', '下げて下さい。'), ('学費を', '払っているのに、'), ('学費を', '高い'), ('下げて下さい。', 'もう少し'), ('払っているのに、', 'つまんないから'), ('高い', 'お金が'), ('高い', '割に')]
depth 3: [('高い', 'お金が'), ('高い', '割に'), ('もう少し', '取り'), ('もう少し', '安く。'), ('もう少し', '安くしませう。'), ('つまんないから', '改善して。'), ('つまんないから', 'とにかく'), ('つまんないから', '講義が'), ('お金が', 'かかりすぎて'), ('割に', '無い。')]
depth 4: [('かかりすぎて', '困ります。'), ('無い。', '意味が'), ('無い。', 'したのに、'), ('無い。', '仕方が'), ('無い。', '全く'), ('無い。', '場が'), ('無い。', '座りにくくて'), ('無い。', '後期履修できないのは'), ('無い。', '授業が'), ('無い。', '特に')]
depth 5: [('全く', '感じない。'), ('全く', '熱望する。'), ('場が', '交流する'), ('座りにくくて', '椅子、'), ('授業が', 'たいがいの'), ('授業が', 'わかりづらい。'), ('授業が', '会計などばかりで、'), ('授業が', '流通に関する'), ('特に', 'なし。'), ('特に', 'ガッカリです。')]
「学費を」からの各単語への経路を探索させる。
パスの長さに応じて色を付けて表示させる。
G = nx.Graph()
G.add_nodes_from(np.unique([data.Term1]+[data.Term2]))
G.add_edges_from([(data.loc[i, 'Term1'], data.loc[i, 'Term2']) for i in range(len(data))])
targets = list(nx.single_target_shortest_path(G, "学費を", cutoff=5).keys())
targets4 = list(nx.single_target_shortest_path(G, "学費を", cutoff=4).keys())
G = nx.Graph()
nodes = targets
G.add_nodes_from(nodes)
G.add_edges_from([(data.loc[i, 'Term1'], data.loc[i, 'Term2']) for i in range(len(data)) if (data.loc[i, 'Term1'] in targets4)|(data.loc[i, 'Term2'] in targets4)])
known = [0] * nx.number_of_nodes(G)
dist = [-1] * nx.number_of_nodes(G)
colors = ['red', 'orange', 'yellow', 'green', 'lightgreen']
color_map = ['black'] * nx.number_of_nodes(G)
start = 0
d = 0
while sum(known) != nx.number_of_nodes(G):
for n in nx.nodes(G):
if nx.shortest_path_length(G, nodes[start], n) == d:
for nb in G.neighbors(n):
if known[nodes.index(nb)] != 1:
dist[nodes.index(nb)] = d + 1
color_map[nodes.index(nb)] = colors[dist[nodes.index(nb)]-1]
known[nodes.index(nb)] = 1
d = d + 1
dist[start] = 0
color_map[start] = 'lightblue'
# ネットワークの可視化
plt.figure(figsize=(40,40))
nx.draw_spring(G, with_labels = True, node_size = 1200, font_size=35, node_color=color_map, width=2, font_family='MS Gothic')
plt.show()
深さ優先探索(DFS)は、頂点$v_s$に隣接する距離1の頂点を1つ選び、それに隣接する距離2の頂点のなかからまだ訪れていない1つを選び、さらに隣接する距離3の頂点のなかからまだ訪れていない1つを選び、という順で探索する手法である。
print('DFS:', list(nx.dfs_edges(G, source='学費を'))[:20])
print('traversed nodes:', list(nx.dfs_preorder_nodes(G, source='学費を')))
DFS: [('学費を', '低く/安く'), ('学費を', '下げて下さい。'), ('下げて下さい。', 'もう少し'), ('もう少し', '取り'), ('取り', '単位を'), ('単位を', '取りやすく。'), ('取りやすく。', 'もっと'), ('もっと', '分かり'), ('もっと', '増やして欲しいです。'), ('もっと', '安く。'), ('安く。', '学食を'), ('学食を', 'しろ。'), ('安く。', '教科書を'), ('教科書を', '使え。'), ('教科書を', '指定して欲しい。'), ('もっと', '安くして欲しい。'), ('もっと', 'ある'), ('もっと', 'いい'), ('もっと', 'とれるようにして欲しい。'), ('もっと', 'やりやすい')]
traversed nodes: ['学費を', '低く/安く', '下げて下さい。', 'もう少し', '取り', '単位を', '取りやすく。', 'もっと', '分かり', '増やして欲しいです。', '安く。', '学食を', 'しろ。', '教科書を', '使え。', '指定して欲しい。', '安くして欲しい。', 'ある', 'いい', 'とれるようにして欲しい。', 'やりやすい', 'アルバイトなど、', 'ゴージャスにして欲しい。', 'スムーズに', '作って欲しい。', '入ればいいのですが。', '出来るように', '出来れば良い。', '参加できるような', '取り易い', '増やして欲しい。', '多くする', '大きい', '大きくしてもらいたい。', '安いと', '安くするべき。', '広く。', '持てて', '援助して欲しい。', '援助するべきだと', '書いて欲しいです。', '楽しくして下さい。', '欲しい。', '現実的な', '簡単に', '緩やかにして欲しい。', '良くなって欲しい。', '難しい', '高くしてほしいです。', 'くれ。', '下さい。', '取らせてください。', '易くして欲しい。', '易くして。', '易くしてください', '（出席なしで）。', '安くしませう。', '払っているのに、', 'つまんないから', '改善して。', 'とにかく', '講義が', '取れるようにして欲しい', '間に', '受けている', '夜なので…）', '又は、', '終わってしまい、', 'いつも', '困っています。', '自己満足で、', '高い', 'お金が', 'かかりすぎて', '困ります。', '割に', '無い。', '意味が', 'ない', 'セミスター制導入の', 'わからない。', '授業の', '来た', 'したのに、', 'セスター制に', '仕方が', '悪い。', '板書の', '全く', 'ない。', '授業が', 'たいがいの', 'わかりづらい。', '会計などばかりで、', '流通に関する', '感じない。', '熱望する。', '場が', '交流する', '座りにくくて', '椅子、', '後期履修できないのは', '特に', 'なし。', 'ガッカリです。']
ダイクストラのアルゴリズム
辺のコストが異なる場合の最短経路探索には、ダイクストラのアルゴリズムが用いられる。
例としてアンケートデータの例で計算させるが、特に意味はない。
「学費を」からの各単語への最短経路を探索させた。
import functools
import operator
data['weight'] =data['度数'].max() - data['度数']
data.loc[data['weight']==0, 'weight'] = 0.01
G = nx.Graph()
G.add_nodes_from(targets)
G.add_weighted_edges_from([(data.loc[i, 'Term1'], data.loc[i, 'Term2'], data.loc[i, 'weight']) for i in range(len(data)) if (data.loc[i, 'Term1'] in targets4)|(data.loc[i, 'Term2'] in targets4)])
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)} #エッジラベルの描画時に'weight'の表示を無くすための工夫
plt.figure(figsize=(50,50))
pos = nx.spring_layout(G, k=0.5,iterations=30)
nx.draw_networkx_edges(G, pos);
nx.draw_networkx_nodes(G, pos);
nx.draw_networkx_edge_labels(G, pos, font_size=20, edge_labels=edge_labels);
nx.draw_networkx_labels(G, font_size=30, pos=pos, font_family='MS Gothic');
dist_estimate = [999] * nx.number_of_nodes(G)
dist_certainty = [0] * nx.number_of_nodes(G)
dist_estimate[0] = 0
while functools.reduce(operator.mul, dist_certainty) == 0:
min_V = 999
for n in nx.nodes(G):
if (dist_certainty[nodes.index(n)]==0) and (dist_estimate[nodes.index(n)]<=min_V):
min_V = dist_estimate[nodes.index(n)]
min_id = n
dist_certainty[nodes.index(min_id)] = 1
for nb in G.neighbors(min_id):
new_estimate = G[min_id][nb]['weight'] + dist_estimate[nodes.index(min_id)]
if new_estimate < dist_estimate[nodes.index(nb)]:
dist_estimate[nodes.index(nb)] = new_estimate
print(dist_estimate)
print(dist_certainty)
[0, 0.01, 19.0, 19.0, 19.0, 38.0, 38.0, 38.0, 38.0, 57.0, 57.0, 57.0, 57.0, 57.0, 57.0, 57.0, 57.0, 73.0, 74.0, 75.0, 76.0, 76.0, 74.0, 76.0, 76.0, 76.0, 76.0, 76.0, 76.0, 75.0, 76.0, 76.0, 76.0, 76.0, 76.0, 76.0, 76.0, 76.0, 91.0, 92.0, 92.0, 92.0, 92.0, 92.0, 92.0, 92.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 93.0, 95.0, 93.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 93.0, 94.0, 94.0, 94.0, 94.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0, 95.0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
最大流最小カット
水道管や交通網のネットワークにおいて、それぞれの辺を通れる水量や交通量に上限が定めらえている場合を考える。
２頂点間のパスをなくすために、取り外す最小の辺集合を最小カットと呼ぶ。
G = nx.DiGraph()
G.add_edge('s', 'a', capacity=3.0)
G.add_edge('s', 'b', capacity=1.0)
G.add_edge('a', 'c', capacity=3.0)
G.add_edge('b', 'c', capacity=5.0)
G.add_edge('b', 'd', capacity=4.0)
G.add_edge('d', 'e', capacity=2.0)
G.add_edge('c', 't', capacity=2.0)
G.add_edge('e', 't', capacity=3.0)
plt.figure(figsize=(5,5))
pos = nx.spring_layout(G)
nx.draw_networkx_edges(G, pos);
nx.draw_networkx_nodes(G, pos);
nx.draw_networkx_edge_labels(G, pos, font_size=16, edge_labels={(i, j): w['capacity'] for i, j, w in G.edges(data=True)});
nx.draw_networkx_labels(G, pos=pos, font_family='MS Gothic');
flow_value, flow_dict = nx.maximum_flow(G, 's', 't')
print('flow value from s to t:', flow_value)
print('the value of flow through edge s-b:', flow_dict['s']['b'])
print('the value of flow through edge s-a:', flow_dict['s']['a'])
cut_value, partition = nx.minimum_cut(G, 's', 't')
reachable, non_reachable = partition
print('min cut value between s and t:', cut_value)
print('reachable nodes from s:', reachable)
print('unreachable nodes from s:', non_reachable)
flow value from s to t: 3.0
the value of flow through edge s-b: 1.0
the value of flow through edge s-a: 2.0
min cut value between s and t: 3.0
reachable nodes from s: {'c', 's', 'a'}
unreachable nodes from s: {'e', 't', 'b', 'd'}
参考文献