Python networkxで情報伝播グラフを可視化する

グラフデータに対して情報伝播を可視化していく実装を記録しておきます。

基底グラフ

予めnetworkxで以下のグラフを作成しているものとします。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()

# ノードとエッジの作成処理
# ...略

nx.draw_networkx(G, node_color="k", edge_color="k", font_color="w")
plt.show()

ユーザ20人に対する関係のつながり

このグラフにnode_0を開始点として10%の確率で情報が伝播していくグラフをシミュレーションする。

また、関連性データは以下のようなフォーマットとしています。

import pandas as pd

df_links = pd.read_csv("links.csv")
df_links.head()

このような20 * 20の関係性(0:無関係、1:関係あり)の表データ。

確率関数とシミュレーション関数

import numpy as np

# percent:伝播確率を元に伝播する/しないを判断する関数
def determine_link(percent):
    rand_val = np.random.rand()
    if rand_val <= percent:
        return 1
    else:
        return 0

# 伝播のシミュレーション関数
# num:シミュレーション人数、list_active:伝播済みノードを格納, percent_percolation:伝播確率
def simulate_percolation(num, list_active, percent_percolation):
    for i in range(num):
        # 情報を知っている人が友人に伝達する
        if list_active[i] == 1:
            for j in range(num):
                node_name = "Node" + str(j)
                # 友人に対して
                if df_links[node_name].iloc[i]==1:
                    # 与えられた確率によって伝播する
                    if determine_link(percent_percolation)==1:
                        list_active[j] = 1
    return list_active

伝播の可視化グラフのプロット

伝播済みのノードは"赤く"表示する関数

# t:可視化するシミュレーション回数, list_timeSeries:伝播ログ
def active_node_coloring(t, list_timeSeries):
    list_color = []
    for i in range(len(list_timeSeries[t])):
        # 指定シミュレーション時に伝播済みのノードは"赤く"する
        if list_timeSeries[t][i]==1:
            list_color.append("r")
        else:
            list_color.append("k")
    return list_color

シミュレーションの実行

以下のコードでnode_0を起点に伝播のシミュレーションを行います。

# 伝播確率 10%
percent_percolation = 0.1
# シミュレーション回数
T_NUM = 100
# シミュレーション人数
NUM = len(df_links.index)
# 人に伝わったかを判別したリスト
list_active = np.zeros(NUM)
# 初期値はnode_0一人が情報を知っている
list_active[0] = 1
# 伝播のログ
list_timeSeries = []
# シミュレーションを100回繰り返す
for t in range(T_NUM):
    list_active = simulate_percolation(NUM, list_active, percent_percolation)
    #シミュレーション1回ごとに伝播の広がりを記録
    list_timeSeries.append(list_active.copy())

シミュレーションごとの伝播の可視化

1回目 node_0からスタート

t = 0
nx.draw_networkx(G, font_color="w", node_color=active_node_coloring(t, list_timeSeries))
plt.show()

2回目 変わらず

t = 1
nx.draw_networkx(G, font_color="w", node_color=active_node_coloring(t, list_timeSeries))
plt.show()

3回目10%の確率に当選する

t = 2
nx.draw_networkx(G, font_color="w", node_color=active_node_coloring(t, list_timeSeries))
plt.show()

4回目以降 伝播が広がっていく

4回目

5回目

6回目

12回目 半数以上に伝播

24回目 残り3つ

36回目

起点エッジが2線、10%の伝播率でも12回ほどの接触である程度の広がりを見せることがわかる。

伝播数の時系列グラフ

シミュレーション回数による伝播数の増加グラフ

list_timeSeries_num = []
for i in range(len(list_timeSeries)):
    list_timeSeries_num.append(sum(list_timeSeries[i]))

plt.plot(list_timeSeries_num)
plt.show()

リンク