Network Analysis in Python

Maps are all well and good, but do you know what’s better. Graphs! I’m not talking about pie charts or even bar charts I mean the ones with edges and vertices (also known as networks). In this post, and this code, I’m going to convert a geodataframe of A-roads around St Pauls into a graph and then try to apply some algorithms to that graph. The key python package used in this post is NetworkX

While I might want to do something a bit different next, I want to start with something that already looks like a network. Roads.

Map of roads in the St Pauls Area

This is a map of the A-roads around St-Pauls. While geographically accurate the geodataframe of these roads isn’t the best for doing network analysis, so the first thing to do is convert it to a network.

G = momepy.gdf_to_nx(remove_multipart(A_Road), approach="primal", length="Length")

I can then plot this using matplotlib next to the original map.

Comparison of GDF and network with all nodes kept

That gives us the graph on the right-hand side. The A-road dataset was extracted from a dataframe of all UK roads so there are too many junctions. To do this I wrote some not very good code to find each node with dimension 2 and replace it and the two edges going into it with a single edge with the length of the new edge equal to the sum of the lengths of the two old edges.

Now with a simplified graph

The new graph is less geographically accurate for the roads (junctions are still accurate) but has been simplified to the point where each node is an A-Road junction.

This new graph can be plotted in different ways for different uses.

Circle plot is my favorite

The first is just letting python plot the network without any link to geography, the second is with the junctions (nodes) in the correct place and the final circular plot lets us see which nodes are connected to which other nodes.

Now I want to find the shortest path between these two junctions on my graph marked with red diamonds

How do I get between Trafalgar Square and Whitechapel without taking the number 15 bus?

Networkx has a shortest path function which by default uses Dijkstra’s algorithm. I ran it using default settings and plotted my result.

Which looks a bit strange! By default, the function uses a weight of 1 for each edge rather than the length of the edge. Changing this gives a much more sensible outcome

Which is a much more sensible route by eye. I tried this on a few other routes and it seemed to make sense.

With the river drawn on

How does this compare to Google’s route?

Hmm, they suggest a quite different route. But I’m still happy with what I’ve said.

Network graphs open up lots of other options for analysis, but I don’t understand what a lot of them are and involve words I haven’t heard since university like eigenvector or Laplacian so I’ll leave them for another day.

Leave a Comment

Your email address will not be published. Required fields are marked *