通常のネットワークでは、ノードを通過するNxN最短パスの数に基づいてノードを色分けしたいと考えています。これは文献では応力中心性 (SC) として知られています。
これを行うには、グラフ内の任意の 2 つのノード間のすべてnx.all_shortest_paths()の最短経路を計算する関数を使用します。
問題のネットワークは非常に規則的であるため、ネットワークの規模に関係なく、最短経路の分布は同じパターンに従うべきだと確信しています。
サイズが の場合、9x9以下に示すように、中央ノードが最も「ストレスを受けている」ことは明らかです (白いノード) 。サイズが の場合10x10、この負荷のかかるノードのクラウドは別の場所に移動します。これが Python/計算効果なのか、それとも正常なのかはわかりません。計算に時間がかかるため、これよりも大きなネットワークはテストしていません10x10(この計算では時間の複雑さが指数関数的になるようです)。
これはどのように起こりますか？最も負荷の高いノードが常に中心にあると思います。ネットワークのサイズを大きくすると、これが当てはまらないのはなぜですか? 結局、トポロジーは変更されません (したがって、対称的です)。
画像:
コード：
from __future__ import print_function, division
import numpy
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors
#Creating the network
N=9
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
labels = dict( ((i,j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds.sort()
vals.sort()
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 15)
#Function counting all shortest paths between any two nodes
counts={}
for n in G.nodes(): counts[n]=0
for n in G.nodes():
for j in G.nodes():
if (n!=j):
gener=nx.all_shortest_paths(G,source=n,target=j)
for p in gener:
for v in p: counts[v]+=1
#Plotting the color coded nodes
fig, ax = plt.subplots()
unaltered_shortest_paths = counts.values() #List
nodes = G.nodes()
n_color = numpy.asarray([unaltered_shortest_paths[n] for n in range(len(nodes))])
sc = nx.draw_networkx_nodes(G, pos=pos2, node_color=n_color, cmap='gist_heat',
with_labels=False, ax=ax, node_size=45)
min_val=int(min(unaltered_shortest_paths))
max_val=int(max(unaltered_shortest_paths))
sc.set_norm(mcolors.Normalize(vmin=0,vmax=max_val))
cbar=fig.colorbar(sc)
cbar.set_label('Number of Shortest Paths')
plt.xlim(-2,N+1,5)
plt.xticks(numpy.arange(0, N, 1))
plt.ylim(N+1,-2,5)
plt.yticks(numpy.arange(0, N, 1))
plt.axis('on')
title_string=('Stress Centrality (SC)')
subtitle_string=('Network size: '+str(N)+'x'+str(N))
plt.suptitle(title_string, y=0.99, fontsize=17)
plt.title(subtitle_string, fontsize=9)
plt.xlabel('X')
plt.ylabel('Y')
plt.show()