An Analysis of Real World Infrastructure Network

The Challenge

 

This study focuses on what similarities exist between different types of infrastructure networks (roads, power grids, airlines). Finding similar topographical structures across different networks will increase our understanding of infrastructure networks. Also it can help to development a more accurate null model for such networks.

Airports

Generators, transformers, or substations

Road Intersections

The Solution

 

Infrastructure networks are all around us and help to define our modern world. The effects of road, flight, and power grid networks are seen every time you drive, fly, or use electricity. Many studies have looked at these networks on an individual basis. However, almost none have conducted a cross network analysis.

We aim to compare these networks to determine what properties they have in common, how structures affect a networks performance, and to use these results to develop a better model for infrastructure networks. Finding these properties can lead to an improvement in how infrastructure systems are developed and changed in the future. We hypothesize that there is not only similarities between road and airline networks but also an overlap, in similarity, between different types of infrastructure networks. These similarities might arise because these networks are all designed to reach the same or similar goals. Furthermore; any similarities found might indicate important subnetworks that allow the infrastructures to accomplish their goals.

In our original approach we ask questions that have never before been postulated. The majority of network research is directed towards biological and social areas but we seek to look at how network science could impact infrastructure research and development. We ask what similarities (if any) exist between these networks, what properties make them unique, and how do those traits allow them to best perform their intended functions. We hope that with this information we can go on to improve the efficiently of infrastructure networks in the future.

Power Grids

Airlines

Road Ways

Methods

The data sets we used are public networks that each cover a specific type of infrastructure. Specifically we looked at a US power grid network[8], a EuroRoad network[3], a Chicago transport network[2], road networks for California[1], Texas[6], and Pennsylvania[5] and both a world airport network[4] and a US airport network[7]. We chose these networks because they were easy to find and attempting to compile our own networks was unfeasible for the scope of this project.

Initially we compared alignment free properties of networks, meaning global properties of each network not taking into account how the network might relate to the others. The properties we looked at included clustering, meaning the interaction between a nodes neighbors, the diameter, meaning the distances between pairs of nodes, and the degree distribution, meaning the number of connections each node has. In order to judge these we compared how well different types of models we able to mimic the properties of these networks. The null models we chose to look at were: Erdos-Renyi (ER), Erdos-Renyi Degree-Distribution (ER-DD), Geometric (Geo), and Scale Free. Based on these initial properties we would be able to identify which networks were most similar and the null model that best captured their attributes. Afterwords we will align these networks and see what the overlap looks like and how it compares to aligning the network with it’s best fitting null model to determine it’s significance.

Graph Types

Erdos-Renyi

essentially a random graph taking into account the number of nodes and edges in the orignial network

Erdos-Renyi Degree-Distribution

similarly to Erods-Renyi but also keeps the degree distribution of the nodes the same as the original network

Geometric

places all the nodes on a surface and tries to get a similar edge count by using a certain radius and any nodes that are that distance from each other are connected

Scale-Free

prioritizes making connections to nodes that already have a lot of connections leading to a ”hub” model, with some nodes with much higher degrees than other

Alignment Free Comparison

For the alignment free comparisons we used the GraphCrunch program[14]. We ran this comparing clustering spectra, distance spectra and degree distribution between our network and 10 instance each of the ER, ER- DD, geo and Scale-free model networks. While initially we began running this program on all of our networks, due to the sizes of the state road networks and the time to complete this project we ended up only running it on the other five. Additionally for the two airport models we changed them from directed weighted graphs to being undirected and unweighted for the purpose of seeing overall structure and to make them more comparable to the other networks we were looking at. Based on our initial results it was clear immediately that the networks that behaved the most similarly were the US and world airport networks, seen in Figure 1, and EuroRoad and power grid networks, seen in Figure 2.

Figure 2: Pearson Correlations of differenRteanl-eWtowrldoNretkwomrk aondPerolpserftyor the power grid and EuroRoad networks for the clustering spectra, distance spectra and degree distribution. This shows geo outperforms the other models in a majority of the cases and the trends between these networks are similar across the different properties.

Figure 1: Pearson Correlations of different network models for the airport networks for the clustering spectra, distance spectra and degree distribution. This shows ER-DD outperforms the other models in a majority of the cases and the trends between US airports and world airports are similar across properties.