5.7. Shortest Path Lengths¶
The next step is to compute the characteristic path length,
Here’s a function that takes a graph and returns a list of shortest path lengths, one for each pair of nodes.
def path_lengths(G):
length_map = nx.shortest_path_length(G)
lengths = [length_map[u][v] for u, v in all_pairs(G)]
return lengths
The return value from nx.shortest_path_length
is a dictionary of dictionaries. The outer dictionary maps from each node, u
, to a dictionary that maps from each node, v
, to the length of the shortest path from u
to v
.
With the list of lengths from path_lengths
, we can compute
def characteristic_path_length(G):
return np.mean(path_lengths(G))
And we can test it with a small ring lattice:
>>> lattice = make_ring_lattice(3, 2)
>>> characteristic_path_length(lattice)
1.0
In this example, all 3 nodes are connected to each other, so the mean path length is