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

個人開発したアプリの宣伝
目的地が設定できる手帳のような使い心地のTODOアプリを公開しています。
Todo with Location

Todo with Location

  • Yoshiko Ichikawa
  • Productivity
  • Free

スポンサードリンク

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

基底グラフ

予め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人に対する関係のつながり

f:id:letitride:20200717113205p:plain:w500

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


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

import pandas as pd

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

f:id:letitride:20200717114044p:plain:w500

このような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()

f:id:letitride:20200717115554p:plain:w500


2回目 変わらず

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

f:id:letitride:20200717115731p:plain:w500


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

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

f:id:letitride:20200717115848p:plain:w500

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

4回目

f:id:letitride:20200717120029p:plain:w500

5回目

f:id:letitride:20200717120052p:plain:w500

6回目

f:id:letitride:20200717120128p:plain:w500

12回目 半数以上に伝播

f:id:letitride:20200717120401p:plain:w500

24回目 残り3つ

f:id:letitride:20200717120506p:plain:w500

36回目

f:id:letitride:20200717120556p:plain:w500


起点エッジが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()

f:id:letitride:20200717124647p:plain:w500