使用Networkx计算顶点所属的最短路径数的更快方法 [英] Faster way to calculate the number of shortest paths a vertex belongs to using Networkx
问题描述
我正在考虑顶点 i 的压力是 i 所属的所有顶点对之间的最短路径数。
我正在尝试使用Networkx来计算它，到目前为止我已经用三种方法进行了计算。 可读，脏和最脏，但它们都不是很快。实际上，我希望它比。 rel =nofollow> betweenness （来源）在Networkx上。有没有更好的方法来计算？对于任何建议，回答或评论，预先感谢。看看我到目前为止做了什么：
Ps .: 此处是一个代码准备好的代码，如果你想尝试一下，再次感谢。
以下是所有版本的常见部分： p>
将networkx作为nx
从集合中导入import defaultdict
最简单，自己动手：
def stress_centrality_dirtiest（g）：
stress = defaultdict（int）
for nx.nodes_iter（g）：
for b in nx.nodes_iter（g）：
如果a == b：
continue
＃pred = nx.predecessor（G，b）＃对于未加权图
pred，距离= nx.dijkstra_predecessor_and_distance（g，b）＃对于加权图
如果不是pred.has_key（a）：
return []
path = [[a，0]]
path_length = 1
index = 0
while index> = 0：
n，i = path [inde x]
如果n == b：
用于映射中的顶点（lambda x：x [0]，path [：index + 1]）[1：-1]：
stress [顶点] + = 1
如果len（pred [n]）> i：
index + = 1
if index == path_length：
path.append（[pred [n] [i]，0]）
path_length + = 1
else：
path [index] = [pred [n] [i]，0]
else：
index - = 1
如果index> = 0：
path [index] [4] + = 1
回报压力
脏
def stress_centrality_dirty（g）：
stress = defaultdict（int）
）路径= nx.all_pairs_dijkstra_path（g）
用于paths.values（）中的项目：
用于item.values（）中的元素：
if len（element）> 2：元素[1：-1]中顶点的
：
stress [顶点] + = 1
返回压力
pre $ p $ def $ $ b stress = defaultdict（int）
paths = nx.all_pairs_dijkstra_path（g）
用于nx.nodes_iter（g）中的源代码：
用于nx.nodes_iter中的结尾（g ）：
if source == end：
continue
path = paths [source] [end]
if len（path）> 2：＃路径必须包含至少3个顶点源 - 另一个节点 - 结束
用于路径[1：-1]中的顶点：＃统计发生次数时排除源和结束顶点
压力[顶点] + = 1
返回压力
您在NetworkX中指出的介词代码几乎可以完成您想要的并且可以轻松进行调整。
累积阶段它应该计算压力中心性（未经测试）$ def $ acccumulate_stress（betweenness，S，P，sigma，s） ：
delta = dict.fromkeys（S，0）
while S：
w = S.pop（）
for v in P [w]：
delta [ v] + =（1.0 + delta [w]）
如果w！= s：
betweenness [w] + = sigma [w] * delta [w]
return betweenness
请参阅论文Ulrik Brandes：关于最短路径中心性及其通用计算的变体。社会网络30（2）：136-145，2008. http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
应力中心性算法是算法12。
I am considering that the Stress of a vertex i is the number of shortest paths between all pairs of vertices that i belongs to.
I am trying to calculate it using Networkx, I've made in three ways so far. The readable, dirty, and dirtiest but none of them is fast. Actually, I would like it to be faster than the betweenness (source) present on Networkx. Is there a better way to calculate that? Thanks in advance for any suggestion, answer or comment. Following see what I did so far:
Ps.: Here is a pastie with the code ready to go if you want give it a try, thanks again.
Here is the common part on all versions:
import networkx as nx
from collections import defaultdict
Dirtiest, brace yourselves:
def stress_centrality_dirtiest(g):
stress = defaultdict(int)
for a in nx.nodes_iter(g):
for b in nx.nodes_iter(g):
if a==b:
continue
# pred = nx.predecessor(G,b) # for unweighted graphs
pred, distance = nx.dijkstra_predecessor_and_distance(g,b) # for weighted graphs
if not pred.has_key(a):
return []
path = [[a,0]]
path_length = 1
index = 0
while index >= 0:
n,i = path[index]
if n == b:
for vertex in map(lambda x:x[0], path[:index+1])[1:-1]:
stress[vertex] += 1
if len(pred[n]) > i:
index += 1
if index == path_length:
path.append([pred[n][i],0])
path_length += 1
else:
path[index] = [pred[n][i],0]
else:
index -= 1
if index >= 0:
path[index][4] += 1
return stress
Dirty
def stress_centrality_dirty(g):
stress = defaultdict(int)
paths = nx.all_pairs_dijkstra_path(g)
for item in paths.values():
for element in item.values():
if len(element) > 2:
for vertex in element[1:-1]:
stress[vertex] += 1
return stress
Readable
def stress_centrality_readable(g):
stress = defaultdict(int)
paths = nx.all_pairs_dijkstra_path(g)
for source in nx.nodes_iter(g):
for end in nx.nodes_iter(g):
if source == end:
continue
path = paths[source][end]
if len(path) > 2: # path must contains at least 3 vertices source - another node - end
for vertex in path[1:-1]: # when counting the number of occurrencies, exclude source and end vertices
stress[vertex] += 1
return stress
The betweenness code you pointed to in NetworkX does almost what you want and can be adjusted easily.
In the betweenness function if you call the following (instead of _accumulate_basic) during the "accumulate" stage it should calculate the stress centrality (untested)
def _accumulate_stress(betweenness,S,P,sigma,s):
delta = dict.fromkeys(S,0)
while S:
w = S.pop()
for v in P[w]:
delta[v] += (1.0+delta[w])
if w != s:
betweenness[w] += sigma[w]*delta[w]
return betweenness
See the paper Ulrik Brandes: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf
The stress centrality algorithm is Algorithm 12.
这篇关于使用Networkx计算顶点所属的最短路径数的更快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
