python(networkx)によるネットワーク分析メモ4 グループ

pythonによるネットワーク分析のメモ書きとなります。
networkxを使用します。

内容・コードがまとまっていないので、詳細については参考書の参照をお願いします。

機会があればしっかり勉強していこうと思います。

ネットワーク分割

Kernighan-Linアルゴリズム

まず、与えられたネットワークを任意に2つのグループに分割した状態からスタートする。
分割された各グループから頂点を1つずつ選び、その２頂点の所属グループを交換したときに、グループ間の辺の数が最も減少するような2頂点を交換する、という処理を繰り返すことによって、グループ間の辺の数が少ない分割を得る。

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

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=4).keys())
targets4 = list(nx.single_target_shortest_path(G, "学費を", cutoff=3).keys())

target_idx = np.arange(len(targets))
target_idx4 = np.arange(len(targets4))

target_dict = dict()
for i,k in zip(target_idx, targets):
    target_dict[i]=k

まずは、初期状態を表示する。

G = nx.Graph()

nodes = target_idx
G.add_nodes_from(nodes)
G.add_edges_from([(targets.index(data.loc[i, 'Term1']), targets.index(data.loc[i, 'Term2']))
                     for i in range(len(data)) if (data.loc[i, 'Term1'] in targets4)|(data.loc[i, 'Term2'] in targets4)])

[targets[i] for i in target_idx]

colors = ['red', 'blue', 'green']
pos = nx.spring_layout(G)

# 2つのグループに分ける
init_nodes = np.array_split(G.nodes(), 2)
init_partition = [set(init_nodes[0]), set(init_nodes[1])]
print(init_partition)

color_map_i = ['black'] * nx.number_of_nodes(G)
counter = 0
for c in init_partition:
    for n in c:
        color_map_i[n] = colors[counter]
    counter = counter + 1

plt.figure(figsize=(15,10))
nx.draw_networkx_edges(G, pos);
nx.draw_networkx_nodes(G, pos, node_color=color_map_i);
nx.draw_networkx_labels(G, labels=target_dict, pos=pos, font_family='MS Gothic');
plt.axis('off')

[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}, {19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37}]

コミュニティ分割を行った結果を示す。

from networkx.algorithms.community import kernighan_lin_bisection

lst_b = kernighan_lin_bisection(G, partition=init_partition)
color_map_b = ['black'] * nx.number_of_nodes(G)
counter = 0
for c in lst_b:
    for n in c:
        color_map_b[n] = colors[counter]
    counter = counter + 1

plt.figure(figsize=(15,10))
nx.draw_networkx_edges(G, pos);
nx.draw_networkx_nodes(G, pos, node_color=color_map_b);
nx.draw_networkx_labels(G, labels=target_dict, pos=pos, font_family='MS Gothic');
plt.axis('off')

コミュニティ抽出

ネットワーク分割と異なり、分割数などがあらかじめ与えられずに、ネットワークの密な部分を抽出するアプローチをコミュニティ抽出と呼ぶ。

ラベル伝播

すべての頂点が別々のコミュニティラベルをもった状態を初期状態として、各頂点が周囲の頂点に合わせて自分の所属コミュニティを変更する処理を繰り返すことで、コミュニティを決定する手法である。

モジュラリティ最適化

ネットワークを分割して得られるコミュニティの質を測る指標として、しばしばモジュラリティが用いられる。
$$
Q=\frac{1}{2m}\sum_{ij}(A_{ij}-\frac{k_ik_j}{2m}\delta (c_i,c_j)
$$
ここで、$m$はネットワークの辺の数、$A_{ij}$はネットワークの隣接行列$A$の$(i,j)$成分、$k_i$は頂点$i$の次数、$c_i$は頂点$i$の属するコミュニティのラベル、$\delta(i,j)$はクロネッカーのデルタで$c_i$と$c_j$が等しときに1、それ以外のときに0の値をとる。
コミュニティ抽出の戦略として、このモジュラリティ値が大きくなるようなネットワークの分割を探索するやり方が用いられ、モジュラリティ最適化と呼ばれる。

2種類の分割方法による結果を示す。

from networkx.algorithms.community import greedy_modularity_communities
from networkx.algorithms.community import label_propagation_communities

colors = ['red', 'orange', 'yellow', 'green', 'lightgreen', 'royalblue', 'blue', 'violet']

lst_m = greedy_modularity_communities(G)
color_map_m = ['black'] * nx.number_of_nodes(G)
counter = 0
for c in lst_m:
    for n in c:
        color_map_m[n] = colors[counter]
    counter = counter + 1

plt.figure(figsize=(15,10))
nx.draw_networkx_edges(G, pos);
nx.draw_networkx_nodes(G, pos, node_color=color_map_m);
nx.draw_networkx_labels(G, labels=target_dict, pos=pos, font_family='MS Gothic');
plt.axis('off')

lst_l = label_propagation_communities(G)
color_map_l = ['black'] * nx.number_of_nodes(G)
counter = 0
for c in lst_m:
    for n in c:
        color_map_l[n] = colors[counter]
    counter = counter + 1

plt.figure(figsize=(15,10))
nx.draw_networkx_edges(G, pos);
nx.draw_networkx_nodes(G, pos, node_color=color_map_l);
nx.draw_networkx_labels(G, labels=target_dict, pos=pos, font_family='MS Gothic');
plt.axis('off')

参考文献