When working with spatial networks, both ArcGIS and Python packages such as NetworkX and iGraph are very useful tools. In the past, I have used both tools to help me better understand spatial network topology and network flow. In this blog post, I hope to share with you some cool features that these tools have to offer.
ArcGIS Network Analyst
The Network Analyst extension helps us solve many network problems, such as finding the best route from origins to destinations, finding the closest emergency vehicle or facility, identifying a service area around a location, and many more.
The routing model in Network Analystcan help us identify the best route from an origin to a destination. The locations can be specified interactively by placing points on the screen, entering an address, or using points in an existing feature class or feature layer. It should be noted here that the best route could be the fastest route, shortest route, or the safest route depending on what the chosen impedance is. If the impedance is time, then the best route is the quickest route. The classic Dijkstra's algorithm is used to solve the routing problem.
Image source: ESRI
The service area model within the Network Analyst extension helps define an area that encompasses all accessible streets of a certain impedance. For example, a 10-minute service area of a hospital includes all streets that can be reached within 10-minutes of the hospital.
Image source: ESRI
The goal of the location-allocation model is to find the most efficient way to locate supply points such that certain demand is satisfied. As the name suggests, this is a twofold complex problem that simultaneously finds the best locations for supply points and allocates demand to these points. In ArcMap, the extension offers different problem types to answer specific questions: minimize impedance, maximize coverage, maximize capacitated coverage, minimize facilities, maximize attendance, maximize market share, and target market share. If you are interested in learning more about these different problem types, please refer to this page for more information.
Image source: ESRI
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. There are many useful functions that we can use to build and analyze spatial networks.
For example, the shortest path functions allow us to find the shortest path between two nodes, similar to the routing model in the ArcGIS Network Analyst extension. In addition, they are also able to generate the shortest path between all pairs of nodes (all_shortest_paths), and calculate the average shortest path length for all node pairs (average_shortest_path_length), and whether or not a path is able to connect two nodes (has_path). In my own research, I have used the shortest path function in the past to simulate trips along the transportation networks and record travel time, distance, and the specific route.
Image source: NetworkX Guide
The centrality functions are useful in understanding what nodes/edges are most critical in a network. The word “critical” has a lot of different meanings, leading to many different definitions of centrality: degree centrality, betweenness centrality, eigenvector centrality, closeness centrality, etc. In the past, I have leveraged centrality measures on a multimodal transportation network to better understand the critical nodes or edges. I also overlaid different hazard maps on the networks and evaluated the changes in centrality measures across different disruptions scenarios.
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
Last but not least, the flow functions within NetworkX make it very straightforward for network scientists and engineers to better model network flows. Useful functions include:
maximum_flow, minimum_cut, shortest_augmenting_path, and max_flow_min_cost. If you are interested in checking out more functions that the NetworkX package has to offer, please click here to access the full documentation. In a course project, I leveraged the max flow algorithm to create evacuation routing plans for vulnerable neighborhoods in the San Francisco bay area. I used the neighborhood blocks as origin/supply points and shelters as destination/demand points and demonstrated how this algorithm could help us better evacuate residents in a hazardous event.
1.Hagberg, A., Schult, D. & Swart, P. Proceedings of the Python in Science Conference (SciPy): Exploring Network Structure, Dynamics, and Function using NetworkX. http://conference.scipy.org/proceedings/SciPy2008/paper_2/ (2008).