5.7. Shortest Path Lengths

The next step is to compute the characteristic path length, \(L\), which is the average length of the shortest path between each pair of nodes. To compute it, we will start with a function provided by NetworkX, shortest_path_length. We will use it to replicate the Watts and Strogatz experiment, then we will see how it works.

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 \(L\) like this:

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 \(1\).

You have attempted of activities on this page