はじめに
ネットワーク構造の性質を利用した制御を学習します📚
ネットワーク結合されたシステムの分散制御について
ネットワーク結合されたシステムの分散制御は、現代社会において非常に重要な概念です。
分散制御の主な特徴と利点は以下の通りです。
- 自律性：各ノードが自律的に動作し、局所的な情報に基づいて意思決定を行う
- 拡張性：ノード数の増加に対して柔軟に対応でき、システム全体の性能を維持できる
- 耐故障性：一部のノードに障害が発生しても、システム全体の機能を維持できる
- 適応性：環境の変化に対して、各ノードが自律的に適応することでシステム全体の性能を維持できる
- 通信効率：各ノードが局所的な情報のみを利用することで、通信負荷を減らすことができる
ネットワーク構造の性質を利用する
ネットワーク構造の性質を利用した制御設計を、２つに分けて順にみていきます。
- 固定型ネットワーク上での制御
- 可変型ネットワーク上での制御
固定型ネットワーク上での制御
固定型ネットワークとは、ノード間の接続関係が固定されたネットワークを指します。
固定型ネットワークの代表例
- パワーグリッド（電力網） - 電力網は発電所、変電所、配電設備が互いに固定的に結ばれており、非常に大規模な固定型ネットワーク
- 有線テレビネットワーク - 有線テレビネットワークは特定の地理的エリアに配線され、各家庭や施設にサービスを提供する固定トポロジーを有してる
固定型ネットワークの分散制御
ネットワークのトポロジー（接続構造）の性質を利用して、効率的な分散制御を設計することができます。
-
スペクトル理論に基づく制御：ネットワークのラプラシアン行列のスペクトル（固有値と固有ベクトル）を利用して、システムの安定性や同期性を解析し、最適な制御則を設計します。
-
グラフ理論に基づく制御：ネットワークのグラフ構造（次数分布、クラスター係数、平均経路長など）を利用して、ノード間の情報伝播や影響の広がりを解析し、効率的な制御則を設計します。
-
中心性に基づく制御：ネットワーク内のノードの中心性（次数中心性、固有ベクトル中心性、媒介中心性など）を利用して、重要なノードを特定し、それらを優先的に制御することで、システム全体の性能を向上させます。
実装例
以下は、Pythonを使用してネットワーク構造を制御する例です。
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
# ネットワークの構築
G = nx.Graph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 4), (4, 5), (5, 2)])
# ラプラシアン行列の計算
L = nx.laplacian_matrix(G).toarray()
# スペクトル分解
eigenvalues, eigenvectors = np.linalg.eigh(L)
# 固有値と固有ベクトルを利用した制御則の設計
def spectral_control(G, eigenvectors, k):
n = G.number_of_nodes()
control_input = np.zeros(n)
for i in range(k):
control_input += eigenvectors[:, i]
return control_input
# グラフ理論に基づく制御則の設計
def graph_theoretic_control(G):
centrality = nx.betweenness_centrality(G)
control_input = np.array([centrality[i] for i in range(G.number_of_nodes())])
return control_input
# 中心性に基づく制御則の設計
def centrality_based_control(G):
centrality = nx.degree_centrality(G)
control_input = np.array([centrality[i] for i in range(G.number_of_nodes())])
return control_input
# 制御則の適用
spectral_control_input = spectral_control(G, eigenvectors, 3)
graph_theoretic_control_input = graph_theoretic_control(G)
centrality_based_control_input = centrality_based_control(G)
# ネットワークの可視化
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=500, font_size=20, font_weight="bold")
# 制御入力のプロット
fig, ax = plt.subplots(3, 1, figsize=(8, 12))
ax[0].stem(range(G.number_of_nodes()), spectral_control_input)
ax[0].set_title("Spectral Control Input")
ax[0].set_xlabel("Node")
ax[0].set_ylabel("Control Input")
ax[1].stem(range(G.number_of_nodes()), graph_theoretic_control_input)
ax[1].set_title("Graph-Theoretic Control Input")
ax[1].set_xlabel("Node")
ax[1].set_ylabel("Control Input")
ax[2].stem(range(G.number_of_nodes()), centrality_based_control_input)
ax[2].set_title("Centrality-Based Control Input")
ax[2].set_xlabel("Node")
ax[2].set_ylabel("Control Input")
plt.tight_layout()
plt.show()
可変型ネットワーク上での制御
可変型ネットワークとは、ノード間の接続関係が時間とともに変化するネットワークを指します。
可変型ネットワークの代表例
- 携帯電話などのモバイルデバイスは、移動することによって異なる携帯電話基地局と接続されるため、ネットワークの構造が常に変化します。
- 農業、環境モニタリング、災害対応などで使われるセンサーネットワークは、センサーの追加や除去、環境の変化に応じてネットワークの接続が変わることがあります。
- 自動車間通信（V2V）や車両とインフラ（V2I）間の通信を含む車両ネットワークも、車両の移動によりネットワークの接続が継続的に変わります。
可変型ネットワークの分散制御
ネットワーク構造自体を制御することで、システムの性能を向上させることができます。
-
適応的ネットワーク制御：ノード間の接続関係を動的に変化させることで、環境の変化に適応し、システムの性能を維持または向上させます。例えば、負荷分散やエネルギー効率の観点から、最適なネットワーク構造を逐次的に探索・構築します。
-
自己組織化ネットワーク制御：ノード間の局所的な相互作用に基づいて、自律的にネットワーク構造を形成・維持します。例えば、スケールフリーネットワークやスモールワールドネットワークなど、望ましい性質を持つネットワーク構造を自己組織的に生成します。
-
ネットワーク構造の最適化：与えられた目的関数（性能指標）を最大化または最小化するようなネットワーク構造を探索します。例えば、ネットワークの同期性や頑健性を最大化するための構造最適化問題を解きます。
実装例
以下は、Pythonを使用してネットワーク構造を制御する例です。
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
# 適応的ネットワーク制御
def adaptive_network_control(G, iterations):
for i in range(iterations):
# ノード間の負荷を計算
load = dict(nx.degree(G))
# 負荷の高いノードから負荷の低いノードへエッジを張り替える
nodes = list(G.nodes())
for _ in range(G.number_of_edges()//10):
high_load_node = max(nodes, key=lambda x: load[x])
low_load_node = min(nodes, key=lambda x: load[x])
neighbors = list(G.neighbors(high_load_node))
if neighbors:
G.remove_edge(high_load_node, neighbors[0])
G.add_edge(high_load_node, low_load_node)
load[high_load_node] -= 1
load[low_load_node] += 1
return G
# 自己組織化ネットワーク制御
def self_organizing_network_control(n, m, iterations):
G = nx.barabasi_albert_graph(n, m)
for _ in range(iterations):
# エッジの重みを計算
weights = dict(nx.degree(G))
# 重みの低いエッジを削除し、新しいエッジを追加
edges = list(G.edges())
for _ in range(G.number_of_edges()//10):
if edges:
edge = min(edges, key=lambda x: weights[x[0]] + weights[x[1]])
G.remove_edge(*edge)
edges.remove(edge)
G.add_edge(np.random.choice(G.nodes()), np.random.choice(G.nodes()))
return G
# ネットワーク構造の最適化
def optimize_network_structure(G, objective_function, iterations):
best_G = G.copy()
best_score = objective_function(best_G)
for _ in range(iterations):
G_candidate = best_G.copy()
# ランダムにエッジを追加または削除
if np.random.random() < 0.5:
u, v = np.random.choice(G_candidate.nodes(), 2)
if not G_candidate.has_edge(u, v):
G_candidate.add_edge(u, v)
else:
edges = list(G_candidate.edges())
if edges:
u, v = edges[np.random.randint(len(edges))]
G_candidate.remove_edge(u, v)
score = objective_function(G_candidate)
if score > best_score:
best_G = G_candidate.copy()
best_score = score
return best_G
# 同期性を評価する目的関数
def synchronizability(G):
L = nx.laplacian_matrix(G).toarray()
eigenvalues = np.linalg.eigvalsh(L)
return eigenvalues[-1] / eigenvalues[1]
# サンプルグラフの生成
G = nx.watts_strogatz_graph(50, 4, 0.1)
# 適応的ネットワーク制御の適用
adapted_G = adaptive_network_control(G.copy(), 100)
# 自己組織化ネットワーク制御の適用
self_organized_G = self_organizing_network_control(50, 2, 100)
# ネットワーク構造の最適化
optimized_G = optimize_network_structure(G.copy(), synchronizability, 100)
# ネットワークの可視化
fig, ax = plt.subplots(2, 2, figsize=(12, 12))
ax[0, 0].set_title("Original Network")
nx.draw(G, ax=ax[0, 0], with_labels=True, font_weight="bold")
ax[0, 1].set_title("Adapted Network")
nx.draw(adapted_G, ax=ax[0, 1], with_labels=True, font_weight="bold")
ax[1, 0].set_title("Self-Organized Network")
nx.draw(self_organized_G, ax=ax[1, 0], with_labels=True, font_weight="bold")
ax[1, 1].set_title("Optimized Network")
nx.draw(optimized_G, ax=ax[1, 1], with_labels=True, font_weight="bold")
plt.tight_layout()
plt.show()
このコードでは、以下の手順でネットワーク構造の制御を実装しています。
-
適応的ネットワーク制御：
adaptive_network_control関数で、ノード間の負荷を計算し、負荷の高いノードから負荷の低いノードへエッジを張り替えることで、ネットワーク構造を適応的に変化させます。 -
自己組織化ネットワーク制御：
self_organizing_network_control関数で、Barabási-Albertモデルを使用して初期のスケールフリーネットワークを生成し、エッジの重みに基づいて重みの低いエッジを削除し、新しいエッジを追加することで、自己組織的にネットワーク構造を形成します。 -
ネットワーク構造の最適化：
optimize_network_structure関数で、与えられた目的関数（ここでは同期性を評価するsynchronizability関数）を最大化するようなネットワーク構造を探索します。ランダムにエッジを追加または削除し、目的関数の値が改善された場合、そのネットワーク構造を採用します。 -
サンプルグラフの生成：Watts-Strogatzモデルを使用して、スモールワールドネットワークを生成します。
-
各手法の適用：生成したサンプルグラフに対して、適応的ネットワーク制御、自己組織化ネットワーク制御、およびネットワーク構造の最適化を適用します。
-
ネットワークの可視化：元のネットワークと、各手法によって制御されたネットワークを可視化します。
ネットワーク内の伝播モデル
ネットワーク内の伝播モデルは、情報、感染症、影響力などがネットワーク上でどのように広がるかを理解するために重要です。
以下は、代表的なネットワーク伝播モデルとそのPythonでの実装例です。
SIRモデル（感染症伝播モデル）：
- S（感受性）、I（感染）、R（回復）の3つの状態を持つノードを考える
- 感染ノードは、隣接する感受性ノードに一定の確率で感染を広げる
- 感染ノードは、一定の確率で回復状態に移行する
実装例
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
def sir_model(G, beta, gamma, num_steps):
# ノードの状態を初期化
for node in G.nodes():
G.nodes[node]['state'] = 'S'
# 初期の感染ノードを選択
initial_infected = np.random.choice(G.nodes(), size=1)
for node in initial_infected:
G.nodes[node]['state'] = 'I'
# 感染の広がりをシミュレート
for _ in range(num_steps):
infected_nodes = [node for node in G.nodes() if G.nodes[node]['state'] == 'I']
for node in infected_nodes:
neighbors = list(G.neighbors(node))
for neighbor in neighbors:
if G.nodes[neighbor]['state'] == 'S' and np.random.random() < beta:
G.nodes[neighbor]['state'] = 'I'
if np.random.random() < gamma:
G.nodes[node]['state'] = 'R'
# 結果を可視化
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node in G.nodes() if G.nodes[node]['state'] == 'S'], node_color='blue', label='Susceptible')
nx.draw_networkx_nodes(G, pos, nodelist=[node for node in G.nodes() if G.nodes[node]['state'] == 'I'], node_color='red', label='Infected')
nx.draw_networkx_nodes(G, pos, nodelist=[node for node in G.nodes() if G.nodes[node]['state'] == 'R'], node_color='green', label='Recovered')
nx.draw_networkx_edges(G, pos)
plt.legend()
plt.show()
# サンプルグラフの生成
G = nx.watts_strogatz_graph(100, 4, 0.1)
# SIRモデルの適用
sir_model(G, beta=0.1, gamma=0.05, num_steps=20)
線形閾値モデル（影響力伝播モデル）：
- 各ノードは、隣接ノードからの影響力の合計が閾値を超えると状態を変化させる
- ノードの状態は、非アクティブ（0）とアクティブ（1）の2つの状態を持つ
実装例
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
def linear_threshold_model(G, thresholds, num_steps):
# ノードの状態を初期化
for node in G.nodes():
G.nodes[node]['state'] = 0
# 初期のアクティブノードを選択
initial_active = np.random.choice(G.nodes(), size=1)
for node in initial_active:
G.nodes[node]['state'] = 1
# 影響力の伝播をシミュレート
for _ in range(num_steps):
inactive_nodes = [node for node in G.nodes() if G.nodes[node]['state'] == 0]
for node in inactive_nodes:
neighbors = list(G.neighbors(node))
active_neighbors = [neighbor for neighbor in neighbors if G.nodes[neighbor]['state'] == 1]
if len(active_neighbors) / len(neighbors) >= thresholds[node]:
G.nodes[node]['state'] = 1
# 結果を可視化
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, nodelist=[node for node in G.nodes() if G.nodes[node]['state'] == 0], node_color='blue', label='Inactive')
nx.draw_networkx_nodes(G, pos, nodelist=[node for node in G.nodes() if G.nodes[node]['state'] == 1], node_color='red', label='Active')
nx.draw_networkx_edges(G, pos)
plt.legend()
plt.show()
# サンプルグラフの生成
G = nx.watts_strogatz_graph(100, 4, 0.1)
# 閾値の設定
thresholds = {node: np.random.uniform(0.2, 0.8) for node in G.nodes()}
# 線形閾値モデルの適用
linear_threshold_model(G, thresholds, num_steps=5)
これらのモデルは、ネットワーク内の伝播現象を理解するための基本的な例です。
実際のシステムでは、より複雑な伝播モデルや、ネットワークの構造とダイナミクスを考慮したモデルが用いられることがあります。また、伝播モデルをシミュレーションするだけでなく、伝播を制御したり、最適な介入戦略を見つけたりするための研究も行われています。
バス・モデル（Bass Model）
- 新製品の普及過程を記述するモデル。
- 革新者（自発的に製品を採用する人）と模倣者（他者の影響で製品を採用する人）の2種類の消費者を考慮
- 累積採用者数の時間変化を、微分方程式で表現
- 新製品の売上予測や価格設定、プロモーション戦略の立案に活用。
import numpy as np
import matplotlib.pyplot as plt
def bass_model(p, q, m, periods):
# 時間による採用者数の配列を初期化
adoptions = np.zeros(periods)
# 最初の期間の採用者数を計算（革新者による採用）
adoptions[0] = p * m
for t in range(1, periods):
# t期における新規採用者数の計算
# 革新係数pと、過去の累積採用者に基づく模倣係数qによって決定
adoptions[t] = (p + q * adoptions[:t].sum() / m) * (m - adoptions[:t].sum())
return adoptions
# パラメータの設定
p = 0.03 # 革新係数: 新製品を独立して採用する人の割合
q = 0.4 # 模倣係数: 他人の影響を受けて製品を採用する人の割合
m = 1000 # 潜在的な市場規模: 製品が到達可能な全体の顧客数
periods = 50 # シミュレーション期間: モデルを実行する時間の長さ
# バス・モデルの実行
adoptions = bass_model(p, q, m, periods)
# 累積採用者数の計算
cumulative_adoptions = np.cumsum(adoptions)
# 結果の可視化
plt.figure(figsize=(10, 6))
plt.plot(range(periods), adoptions, label='Adoptions') # 期間ごとの新規採用者数
plt.plot(range(periods), cumulative_adoptions, label='Cumulative Adoptions') # 累積採用者数
plt.xlabel('Time')
plt.ylabel('Number of Adopters')
plt.title('Bass Diffusion Model')
plt.legend()
plt.grid(True)
plt.show()
線形閾値モデル（Linear Threshold Model）
- 個人の意思決定が、周囲の人々の影響を受けて行われるという仮定に基づくモデル
- 各個人が情報を受け入れる閾値を持ち、周囲の採用者の割合がその閾値を超えると情報を受け入れる
- ネットワーク構造上での情報伝播をシミュレーションできる
- 口コミ marketing や、ソーシャルネットワーク上での情報拡散の分析に応用
import random
import networkx as nx
import matplotlib.pyplot as plt
def linear_threshold_model(G, threshold, initial_adopters, num_iterations):
# 初期状態でアクティブなノードのセット
active = set(initial_adopters)
for _ in range(num_iterations):
new_active = set()
# 各ノードについて、アクティブになるかどうかをチェック
for node in G.nodes():
if node not in active:
# ノードの全隣接ノードからの重みの合計
total_weight = sum(G[node][neighbor]['weight'] for neighbor in G.neighbors(node))
# アクティブな隣接ノードからの重みの合計
active_weight = sum(G[node][neighbor]['weight'] for neighbor in G.neighbors(node) if neighbor in active)
# アクティブな隣接ノードの重みが閾値を超えた場合、ノードを新たにアクティブとする
if active_weight / total_weight >= threshold:
new_active.add(node)
# 新たにアクティブになったノードを追加
active.update(new_active)
return active
# ネットワークの生成（バラバシ・アルバートモデルによる無向グラフ）
G = nx.barabasi_albert_graph(100, 2)
# エッジの重みをランダムに設定
for edge in G.edges():
G.edges[edge]['weight'] = random.uniform(0, 1)
# パラメータの設定
threshold = 0.3 # アクティブ化のための閾値
initial_adopters = [0, 1, 2] # 最初にアクティブなノード
num_iterations = 5 # イテレーションの回数
# 線形閾値モデルの実行
active_nodes = linear_threshold_model(G, threshold, initial_adopters, num_iterations)
# 結果の可視化
node_colors = ['red' if node in active_nodes else 'blue' for node in G.nodes()]
nx.draw(G, node_color=node_colors, with_labels=True)
plt.show()
独立カスケードモデル（Independent Cascade Model）
- ネットワーク上の情報伝播を確率的にモデル化
- 情報を受け入れた個人が、一定の確率で隣接するノードに情報を伝播させる
- 各ステップで伝播が独立に起こると仮定
- インフルエンサー・マーケティングの効果分析や、バイラル・マーケティング戦略の評価に利用
import random
import networkx as nx
import matplotlib.pyplot as plt
def independent_cascade_model(G, activation_prob, initial_active_nodes, num_iterations):
# 最初にアクティブなノードのセット
active_nodes = set(initial_active_nodes)
# これまでにアクティブになった全ノードのセット
all_activated_nodes = set(initial_active_nodes)
for _ in range(num_iterations):
newly_activated_nodes = set()
# 現在アクティブな各ノードについて、その隣接ノードをチェック
for node in active_nodes:
for neighbor in G.neighbors(node):
# 未アクティブな隣接ノードがアクティブ化するかどうかをランダムに決定
if neighbor not in all_activated_nodes and random.random() < activation_prob:
newly_activated_nodes.add(neighbor)
# 新たにアクティブになったノードを次のステップでのアクティブノードとして更新
active_nodes = newly_activated_nodes
# 新たにアクティブになったノードを全アクティブノードのセットに追加
all_activated_nodes.update(newly_activated_nodes)
return all_activated_nodes
# ネットワークの生成（ワッツ–ストロガッツ小世界ネットワーク）
G = nx.watts_strogatz_graph(100, 4, 0.1)
# パラメータの設定
activation_prob = 0.2 # 各隣接ノードがアクティブ化する確率
initial_active_nodes = [0, 1, 2] # 最初にアクティブなノードのリスト
num_iterations = 5 # シミュレーションの繰り返し回数
# 独立カスケードモデルの実行
activated_nodes = independent_cascade_model(G, activation_prob, initial_active_nodes, num_iterations)
# 結果の可視化
# アクティブノードは赤色、非アクティブノードは青色で表示
node_colors = ['red' if node in activated_nodes else 'blue' for node in G.nodes()]
nx.draw(G, node_color=node_colors, with_labels=True)
plt.show()
SIRモデルの応用
import numpy as np
import matplotlib.pyplot as plt
def sir_information_model(beta, gamma, N, I0, num_steps):
# 感受性のある個体数（情報をまだ受け取っていない人々）
S = np.zeros(num_steps)
# 情報を受け取った個体数
I = np.zeros(num_steps)
# 回復した個体数（情報から離れた人々）
R = np.zeros(num_steps)
# 初期条件の設定
S[0] = N - I0 # 初期の感受性のある個体数
I[0] = I0 # 初期の情報保持者数
R[0] = 1000 # 初期の回復者数は0
for t in range(1, num_steps):
# 次の時点での感受性のある個体数の計算
S[t] = S[t-1] - beta * S[t-1] * I[t-1] / N
# 次の時点での情報保持者数の計算
I[t] = I[t-1] + beta * S[t-1] * I[t-1] / N - gamma * I[t-1]
# 次の時点での回復者数の計算
R[t] = R[t-1] + gamma * I[t-1]
return S, I, R
# パラメータの設定
beta = 0.15 # 情報伝達率、つまり情報が広がる速度
gamma = 0.05 # 情報の風化率、つまり情報を忘れる速度
N = 11000 # 全体の人口
I0 = 400 # 初期の情報保持者数
num_steps = 365 # シミュレーションのステップ数
# SIRモデルの実行
S, I, R = sir_information_model(beta, gamma, N, I0, num_steps)
# 結果の可視化
plt.figure(figsize=(10, 6))
plt.plot(range(num_steps), S, label='Susceptible') # 感受性のある個体の推移
plt.plot(range(num_steps), I, label='Informed') # 情報保持者の推移
plt.plot(range(num_steps), R, label='Recovered') # 回復者の推移
plt.xlabel('Time')
plt.ylabel('Number of Individuals')
plt.title('SIR Information Diffusion Model')
plt.legend()
plt.grid(True)
plt.show()
二段階フロー・モデル（Two-step Flow Model）
- マスメディアと口コミの相互作用を考慮したモデル
- マスメディアから情報を受け取ったオピニオンリーダーが、その情報を周囲の人々に伝達
- オピニオンリーダーの特定と活用が、効果的な情報伝播につながる
- インフルエンサー・マーケティングの理論的基盤となるモデル
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
def two_step_flow_model(G, opinion_leaders, media_exposure, influence_rate, num_iterations):
# メディアに影響されたオピニオンリーダーのセット
media_influenced = set(opinion_leaders)
# 影響を受けた全ノードのセット
all_influenced = set(opinion_leaders)
for _ in range(num_iterations):
newly_influenced = set()
# メディアに影響された各ノードからその隣接ノードに影響が広がるかをチェック
for node in media_influenced:
for neighbor in G.neighbors(node):
# 未影響の隣接ノードが影響を受けるかどうかランダムに決定
if neighbor not in all_influenced and np.random.rand() < influence_rate:
newly_influenced.add(neighbor)
# メディアによる新たな影響を受けるノードの選択
media_influenced = set(np.random.choice(G.nodes(), int(media_exposure * G.number_of_nodes()), replace=False))
# 新たに影響を受けたノードを全影響ノードのセットに追加
all_influenced.update(newly_influenced)
return all_influenced
# ネットワークの生成（ワッツ–ストロガッツ小世界ネットワーク）
G = nx.watts_strogatz_graph(100, 4, 0.1)
# パラメータの設定
opinion_leaders = [0, 1, 2] # オピニオンリーダーとされるノードのリスト
media_exposure = 0.1 # 各イテレーションでメディアの影響を受けるノードの割合
influence_rate = 0.3 # 隣接ノードが影響を受ける確率
num_iterations = 5 # シミュレーションの繰り返し回数
# 二段階フロー・モデルの実行
influenced_nodes = two_step_flow_model(G, opinion_leaders, media_exposure, influence_rate, num_iterations)
# 結果の可視化
# 影響を受けたノードは赤色、それ以外は青色で表示
node_colors = ['red' if node in influenced_nodes else 'blue' for node in G.nodes()]
nx.draw(G, node_color=node_colors, with_labels=True)
plt.show()
