使用networkx计算平均最短路径长度

less than 1 minute read

问题

小可老师给我提了一个问题:为什么一个微博扩散网络的平均最短路径长度是0.001?

平均最短路径长度的定义

给定一个网络G(n, e), n是节点数量,e是链接数量。对于网络中的任意一对节点source s和target t,我们可以计算它们之间的最短距离$d_{s, t}$。将这些距离相加除以$n(n-1)$,就可以得到网络的平均最短路径长度。公式如下1

代码

首先,生成一个实例网络。

import networkx as nx
import matplotlib.pyplot as plt
# 生成一个有向网络
G=nx.DiGraph()
#网络构成
G.add_edges_from([(1, 2), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (6, 7)])
#绘制网络
pos=nx.spring_layout(G, iterations=5000) #设置网络的布局
plt.figure()
nx.draw(G, pos)

avrage—nx-path

这样我们生成了一个较为典型的星形有向扩散网络。

来看一下节点之间的最短路径长度:

nx.average_shortest_path_length(G) # 网络平均最短距离0.181

果然有向网再次出现小于1的平均最短距离。 按照定义,我们需要统计任意一对节点之间的距离,节点1作为起点与其它节点之间的最短距离的和是10, 2是2, 6是1, 其它节点不存在最短路径的问题。 这样 $a =\frac {10 + 2 + 1}{9*8} = 0.181$

上述手工计算过程可以通过nx.all_pairs_shortest_path_length(G)实现。

nx.all_pairs_shortest_path_length(G)
Out[29]:
{1: {1: 0, 2: 1, 3: 2, 4: 2, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1},
 2: {2: 0, 3: 1, 4: 1},
 3: {3: 0},
 4: {4: 0},
 5: {5: 0},
 6: {6: 0, 7: 1},
 7: {7: 0},
 8: {8: 0},
 9: {9: 0}}

由上述结果,可知道对于类似节点3和4之间距离的问题,networkx就是认为不存在的。所以没有列出,测试一下:

nx.shortest_path_length(G, source = 1, target =2)
# 1
nx.shortest_path_length(G, source = 1, target =3)
# 2
nx.shortest_path_length(G, source = 3, target =4)
#error: NetworkXNoPath: No path between 4 and 3.

因为有些节点之间距离不存在而不被计算(被认为是0而非无穷大),所以产生了节点数量的平方大于最短距离之和的情况,进而平均最短距离小于1这种反直觉的情况在有向网络中出现了。

当我们把网络转化为无向网络的时候,这种情况就消失了。

UG=G.to_undirected()
nx.average_shortest_path_length(UG) #1.93

对于这种星形扩散网络,很多节点对之间的最短路径并不存在,应该被计算为无穷大,而不是0,所以对于这种网络计算平均最短路径长度没有太大的意义了。与其如此,不如计算所有节点对当中,不存在最短路径长度的比例。

参考

  1. http://networkx.lanl.gov/reference/generated/networkx.algorithms.shortest_paths.generic.average_shortest_path_length.html