I have always been interested in working with spatial networks. My first introduction to spatial network modeling was in Prof. John Radke’s Geographic Information Systems class when I learned about building and analyzing spatial networks using the Network Analyst extension in ArcMap. This extension provides powerful tools to solve common network problems, such as finding the best route across a city, finding the closest emergency vehicle or facility, identifying a service area around a location, servicing a set of orders with a fleet of vehicles, or choosing the best facilities to open or close. Since ArcMap is a proprietary application that is part of the ArcGIS Desktop suite of software products developed by Esri, a license is required to access all the extensions including Network Analyst. I started to wonder if there exists another publicly available tool that is capable of running similar network analysis. After some research online, I found NetworkX. In this blog post, I will briefly introduce the NetworkX python package, three useful modules that NetworkX offers, and a recent project that I worked on using NetworkX as the main analytical tool.
NetworkX is “a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks1”. The geospatial generators within NetworkX make it easy to build, model, and visualize spatial networks as graph objects using Esri shapefiles and JSON. For example, we can use the read_shp(path[, simplify]) function to generate networkx.DiGraph from shapefiles and use the draw(G) function to create a simple visualization of the graph. I listed below three common modules within NetworkX that are useful in exploring spatial network properties:
-
Degree distribution
Degree distribution provides insights into the network structure and is critical in studying spatial networks. Two common methods to visualize the degree distribution of spatial networks are degree rank plot and degree histogram (Figure 1).
Figure 1: Degree rank and degree histogram plots for a randomly generated network. Source: NetworkX Degree Analysis (with code example)
-
Centrality
In Graph Theory and Network Science, centrality indicators such as betweenness centrality, closeness centrality, degree centrality, eigenvector centrality, etc., provide answers to the same question: ”which nodes within the graph are important?” from different perspectives (Figure 2). Applications include identifying key nodes in road infrastructure networks2 and finding “hubs” in air transportation networks3
Figure 2: Examples of A) Betweenness centrality, B) Closeness centrality, C) Eigenvector centrality, D) Degree centrality, E) Harmonic centrality and F) Katz centrality of the same graph. Source: Wikimedia Commons
-
Shortest paths
The shortest paths module within NetworkX provides a number of ways to compute the shortest paths and path lengths between nodes in the graph. The functions in this module are useful in understanding spatial network characteristics, running travel simulations, and optimizing network flows.
Figure 3: Finding the shortest path (in red) in a graph using the Dijkstra algorithm (NetworkX function: dijkstra_path(G, source, target[, weight])).
The three modules listed above only represent a fraction of the complete suite currently available in NetworkX. If you are interested in learning more NetworkX modules, please feel free to open this site to access full documentation, source codes, and tutorials!
In a recent project, I used NetworkX as my main modeling tool to study the impact of coastal flooding on the fuel transportation network under 120 climate scenarios4. Using the graph generators in NetworkX, I created a comprehensive multi-modal network model representing the fuel supply system in the San Francisco Bay Area (Figure 5 left panel). Then, I spatially overlaid coastal flooding hazard maps on the network to evaluate hazard exposure (Figure 4) and to simulate cascading impacts of local network disruptions (Figure 5 right panel).
Figure 4: Exposure of node and link fuel infrastructure assets to coastal flooding under 120 climate scenarios. The top row displays boxplots of link asset types’ exposure profiles in terms of percentage inundation and the bottom row displays boxplots for node asset types.
Figure 5: Left panel: Topologic visualization of the fuel transportation network in the San Francisco Bay Area. Each circle represents a node within the network. All nodes are color-coded according to the type of asset they represent. The size of the circle corresponds to the degree of each node: bigger circles represent nodes with a higher degree (more connections) whereas smaller circles represent nodes with a lower degree (fewer connections). Right panel: Cascading effects of network failures. Results from network failure simulation show that nodes with smaller degrees could have a bigger impact in terms of total disrupted network nodes and links as well as global network efficiency.
I think NetworkX provides great tools for researchers to study and model spatial networks. I hope this blog post provides a sneak peek into what NetworkX can do. If you are on a hunt for a tool to build, analyze and visualize spatial networks, please consider giving NetworkX a try!
References: