The structure and behaviour of hierarchical infrastructure networks

To generate a clear understanding of the characteristics of existing and emerging graph models, a suite of eight graph models has been generated, culminating in a total of 6038 graphs. The suite extends from networks generated with random graph models (2000 realisations), through scale-free (1000 realisations) and small-world models (1000 realisations), to hierarchical models (2038 realisations). These have been generated using a combination of previously-developed algorithms to create a range of common graph models including the Erdos–Renyi (ER) model (Erdos and Renyi 1959) for random networks, the Watts–Strogatz (WS) (Watts and Strogatz 1998) model for small-world networks, the Barabasi–Albert (BA) model (Barabasi and Albert 1999) for scale-free networks, and the balanced tree model for Tree networks (Fig. 1a); all available in the employed python NetworkX library (NetworkX 2020). For hierarchical networks, three further algorithms have been implemented. Firstly to capture the presence of community structure as found within some hierarchical networks (Ravasz et al. 2002; Yerra and Levinson 2005; Shai et al. 2015; Shekhtman and Havlin 2018), a model devised by Ravasz et al. (2002) and Ravasz and Barabasi (2003) (Fig. 1b) has been implemented. This captures the greater complexities and hierarchical levels compared to the stochastic block model used Shekhtman and Havlin (2018) and that used by Shai et al. (2015) as mentioned earlier which are limited in their number of hierarchical levels. Two further models, variations on the tree model, known as the HR and HR+ models have been developed for this research, with these generating a less structured tree network through the addition of edges to the structure, with the HR model adding edges randomly between nodes and the HR+ model only adding the extra edges between nodes in the same or adjacent levels of the hierarchical tree structure. In both cases, new edges can neither be self-loops or duplicate existing edges. The number of new edges to add is calculated using Eq. 1, where E is number of nodes and p a multiplier between 0 and 1.

A limit of 2000 nodes has been set for the node count of each graph realisation (\(N=2000\)), with realisations from 2 nodes to 2000 being generated so a clear variation on graph structure and complexity is seen within the resultant ensemble. For each graph model 1000 realisations are generated where possible. Those graphs with a more defined structure (such as the Tree and HC models) have no random exponent in their generation, so a limited number of realisations is possible within the set constraints. As a result there 1000 realisations of each model except for the HC model, which has 7 realisations, and the Tree model, which has 31. Examples of each of the models are shown in Fig. 2, where (a) to (d) are to be referred to as non-hierarchical, and (e) to (h) as hierarchical as they all have a tree structure.

These synthetic networks are referred to as ‘graphs’ in the remainder of the paper.

A suite of real world infrastructure networks has been employed covering sectors including road, rail, air, electricity, gas and rivers (Table 1). Spatial network models (Fig. 3) have been developed using a range of geographic datasets for each sector with a suite of spatial tools (see Barr et al. (2013) for more details) used to generate topologically-valid networks and correct any errors (overshoots and undershoots at intersections). These real world examples are referred to as ‘networks’ in the remainder of the paper.

Seven road networks have been generated using the Ordnance Survey Meridian 2 vector dataset covering Great Britain, with more detailed subsets for cities/regions including Tyne and Wear, Leeds, and Milton Keynes. Versions have been generated with different road classes; one only includes motorways, and one includes motorways, A-roads, B-roads and minor roads. Open Street Map (Open Street Map 2012) has also been used to generate road networks covering Ireland, with two versions; one with motorways and trunk roads (\(N=3521\)), and a second with primary roads added (\(N=4444\)). All road networks have been created with nodes with a degree of two removed and the edges dissolved giving a representative topology of the network.

Rail networks have been generated for the UK from the Ordnance Survey Meridian 2 vector dataset, with nine networks created. As well as a national network, smaller light rail networks have been created for suburban systems including the Tyne and Wear Metro (\(N=60\)), Manchester Metrolink (\(N=65\)) and those overseen by Transport for London (TfL) as a composite network (\(N=399\)). Open Street Map data has also been used to generate 7 networks for a range of other rail systems outside of Great Britain, including Ireland (\(N=201\)) and light rail in the cities of Boston (USA) (\(N=120\)) and Paris (France). These have been validated using system maps freely available online from the respective operators.

Six air networks have been generated using data available from OpenFlights (Open Flights 2012), as used in previous studies (Wilkinson et al. 2012; Verma et al. 2014). This set of networks includes those for Europe (\(N=643\)), the UK (\(N=48\)), the USA (\(N=601\)) and North America (\(N=889\)) as well as operator networks, for British Airways (\(N=198\)) and EasyJet (\(N=125\)).

Energy networks are also represented, with data from the National Grid for England and Wales used to build three versions of the network with varying levels of detail, from \(N=\mathrm{23,787}\) to \(N=2218\). A synthetically-generated distribution network has also been used (ITRC 2013), to create a transmission and distribution network (\(N=\mathrm{170,667}\)). The national gas network for Great Britain (\(N=1486\)) is also included.

Using Ordnance Survey Meridian 2 data four river networks have been generated for rivers across Great Britain; Tyne (\(N=616\)), Severn (\(N=1944\)), Dee (\(N=896\)) and Eden (\(N= 302\)).

Finally a network representation of the JANET network (Jisc 2015), a network providing high speed digital connections for UK academic institutions, has been created (\(N=38\)).

Network structure has traditionally been characterised from a topological perspective using metrics such as the degree distribution, clustering coefficient and the average shortest path length (Watts and Strogatz 1998; Barabasi and Albert 1999; Newman 2003b). These metrics have also been used as reference for the subsequent development of graph models such as those for graphs with small-world (Watts and Strogatz 1998) and scale-free (Barabasi and Albert 1999) characteristics. Higher level metrics, such as those beyond the traditionally-used measures above, are more relevant to the functioning of infrastructure networks as they may tell us more information about a network’s behaviour and organisation, potentially helping to characterise real world networks with greater realism (Rozenfeld et al. 2005). For example, statistics about the cycles found in a graph are shown by Rozenfeld et al. (2005) to highlight useful properties of networks with regard to their connectivity which are otherwise missed by traditional metrics, such as the degree distribution.

The continued development of graph algorithms alongside greater computational resources also allows more complex metrics to be computed over large graphs than has been previously possible. These advancements allow for the dynamics of a network to be considered, and not just the topological structure, key when considering infrastructure networks (Luca et al. 2006). For the purpose of this research, three higher-level metrics, detailed in the following paragraphs, have been chosen due to their applicability for characterising graphs/networks.

Characterising how a network may function, or how its structure allows movement and flows to pass over it, provides an insight to how it may operate in delivering a service. Betweenness centrality, first introduced by Freeman (1978), is a measure of the proportion of all shortest paths which pass through each node, providing details on how well connected the network might be (Barthélemy 2004). This measure also provides an insight into the way flows of information or goods may pass over the network (Crucitti et al. 2006; Barthelemy 2011). Betweenness centrality is defined by Brandes (2001) as:where V is the set of nodes, \(v\) being the node of interest, \(\sigma \left(s, t|v\right)\) being the number of shortest paths through node \(v\) and \(\sigma \left(s,t\right)\) the number of shortest paths in the network. The value for each node, between zero and one, is an indicator of the importance of the in the connectivity of the networks, and although the distribution of these values across the network is a useful indicator of how central nodes are to a network (Crucitti et al. 2006), the maximum value \({G}_{{max}_{{C}_{B}}}\) (Eq. 3) alone provides an insight into the connectivity of the graph. Where the maximum value is high, tending close to one, the network can be expected to be reliant on a single node for the network to remain connected, with a high proportion of the shortest paths passing through it. Where the value is close to zero, this suggests that there is much more even distribution of shortest paths across the network indicating a better-connected structure.

Both the number and distribution of cycles has been used previously as a higher-level metric to identify structural characteristics of graphs or networks, allowing new insights to be learned (Watts and Strogatz 1998; Rozenfeld et al. 2005; Costa et al. 2007). A cycle is defined as a path formed of a set of edges, which starts and finishes at the same node, but does not visit the same node or edge more than once (Dolan and Aldous 1993; Caldarelli et al. 2004). Indicating a connected set of nodes, the greater the number of cycles the better connected the graph is likely to be. A tree network, an example of poorly connected graph, has no cycles (Albert and Barabasi 2002). The length and propensity of cycles can give an indication of the characteristics of a graph, with a greater frequency of short cycles alone suggesting a better connected graph, while longer cycles suggest a lesser connected topological structure (Lind et al. 2005; Klemm and Stadler 2006). In this paper we adopt the measure of cycle basis, the fundamental set of cycles from which all cycles can be formed (Paton 1969; Diestel and Kühn 2004), to characterise the connectedness of the graph accounting for cycles of all lengths. To accommodate for the different cardinality of graphs or networks, the count of the number of cycle basis (\(\sum CB\)) is normalised by the number of nodes (\(\sum N\)), to give a value for comparison across all graphs (\(\overline{CB }\)), Eq. 4.

The final metric used is the assortativity coefficient, a global measure of the similarity of the degree of neighbouring nodes in a graph, characterising how the network is connected at a neighbourhood level (Newman 2003a). This is defined by Newman (2003a) aswhere e_ij is the fraction of all edges which join nodes with degree x and degree y, a_i and b_j are the fraction of edges that start and end at nodes with degree x and y respectively and σ_a and σ_b are the standard deviation of the distributions a_i and b_j. A returned value, between − 1 and 1, which is closer to one indicates an assortative network where nodes are connected to those of a similar degree, indicative of a regular structure, compared to those near negative one which suggest a hub and spoke structure (Newman 2003a). The ability of the metric to distinguish the characteristics of the underlying structure also allows it to be applied as an indicator of network robustness (Newman 2002; Foster et al. 2010).

The three metrics described above (the maximum betweenness centrality, the number of cycle basis and the assortativity coefficient) give insights into the characteristics of networks from different perspectives, providing measures of how well connected a graph is, how the structure of the graph affects flows over it and how robust the graph may be to perturbations. It is important to select those metrics which are important to answering the aim of this work (Newman 2003b), and this combination of higher-level metrics provide more details on the structure, characteristics, and potential behaviour than possible through some more traditional methods, such as the aforementioned degree distribution and shortest average path length, while also providing other insights, and thus we use these three metrics alone for our analysis.

Following the computation of the metrics described, the similarity of the distribution of the values for each graph type was statistically tested using the multivariate transformed divergence statistic which assesses the amount of overlap between the distributions of the values. Singh (1984) defines this aswherewhere i and j are the two data classes, C_i is the covariance matrix of i, u_i the mean vector of i, tr the trace function and T the transposition function. Where TD = 100, the distributions are statistically different, where TD = 0, the distributions are statistically identical. Typically, where TD ≥ 85, the distributions are said to be statistically different (Swain and Davis 1978).

To further understand the characteristics of the suite of synthetic and infrastructure networks, their robustness to failure is explored to give further insights into their topological structure. Using common iterative failure methods, such as those employed by Albert et al. (2000) and Holme et al. (2002) where at each iteration a node is selected to be removed, the ability of each synthetic graph type to topologically withstand the perturbations can be compared, along with the responses from the infrastructure networks.

Three common node selection methodologies are used (Albert et al. 2000; Holme et al. 2002; Luca et al. 2006; Lordan et al. 2014); a random node selection method where at each iteration a node is randomly selected to be removed; a node degree-based method where the node with the greatest degree (or one with the joint greatest degree) is removed at each iteration; and the third where the node with the greatest betweenness centrality is removed at each iteration. Please see Albert et al. (2000), Holme et al. (2002) or Luca et al. (2006) for more information. For the latter two methodologies the values are recalculated at each iteration to ensure the greatest impact (Luca et al. 2006), and in all three cases the graphs/networks are perturbed until \(E=0\).

To explore the characteristics of both the graphs and networks, an ensemble analysis is performed where five simulations for each failure methodology are performed for every graph or network to account for the random exponent in the failure models; the random selection of a node in the random model, or the random selection of a joint highest rated node in the other two models. A total of fifteen simulations are therefore run for each graph or network, where the performance is recorded using graph metrics, averaged across the five simulations.

The failure of the graph or network is measured with respect to how quickly it becomes disconnected and fragments into subgraphs or communities of nodes. Therefore, the more robust a graph is the fewer subgraphs would be expected to form. Other measures could be considered, such as the size of the giant component (the largest connected subgraph) (Holme et al. 2002), as an alternative measure of the effect perturbations have on a graph/network (Albert et al. 2000; Holme et al. 2002). This measure, however, only provides an indicator as to how large the largest component of the network remains, and does not give an indication as to the state of the remaining aspects of the network. In an infrastructure context, any connected components outside the giant component could still provide a service to users and thus should not be ignored entirely from an analysis of the resilience of a network. Where there is a high number of subgraphs, it suggests the network has fragmented into many small subgraphs, where these may remain of use to geographical areas local to such parts of the graph or network.

The three graph metrics described earlier were calculated for each of the graphs and networks in the study. The results show that there is distinguishable difference in metric values between the synthetic hierarchical and non-hierarchical graph models (Fig. 4). This was most apparent when the distributions of the assortativity coefficient (AC) were plotted against the maximum betweenness centrality (MBC). Here the single standard deviation ellipses for each of the graph models for the distribution of the metric values indicate a clear separation between the hierarchical and non-hierarchical models (Fig. 4a). This is also shown statistically, where there is also no statistical similarity in the distributions of the metric values for the AC/MBC for each pair-wise combination of graph models (Table 2). The same pattern and statistical separation between the non-hierarchical and hierarchical models is also shown through the distributions for the other two metric combinations though with less clarity.

With the AC-MBC distributions the hierarchical models, \(\overline{AC }\)≤ − 0.17 and \(\overline{MBC }\) ≥ 0.25, are distinct from the non-hierarchical, − 0.04 ≤ \(\overline{AC }\) ≤ 0.0 and 0.01 ≤ \(\overline{MBC }\)≤ 0.08, with the TREE and HC models especially shown to disparate in structure,\(\overline{MBC }\)≥ 0.5. This relationship can be explained by the number of cycle basis per nodes (CB) present in the different networks, with a tendency to be more prevalent in non-hierarchical graphs, \(\overline{CB }>7\), than hierarchical graphs, \(0>\overline{CB }<1\), where a low CB count suggests a greater MBC value (Fig. 4c). Due to the lower number of CB, there are fewer connections and thus a greater dependency on those nodes with connections, generating a greater MBC value. This can be seen with the values returned for the TREE and HC models where \(\overline{CB }<2\) and \(\overline{MBC }\)= 0.765. The effect of the extra edges being added to the TREE graph for the HR and HR+ models reduces the CB value, \(\overline{CB }<1,\) and therefore the resultant MBC value.

The statistical relationship between the hierarchical and non-hierarchical model groups is disparate (Table 2), with the pair-wise relationships between these two groups all returning values over 97, when a value above 75 indicates no similarity in the distributions. A small number of the relationships between graph models, such as between the hierarchical HR and HR+ models, show similarity for all three metric distributions (39.84, 27.34, 6.53, indicated by † in Table 2) from which we can infer a degree of similarity in the characteristics of the models. This relationship was expected as both models have their origins in the TREE model and the generation algorithms only varying slightly. The other greatest similarity between graph models is found to be for the non-hierarchical BA-WS models, returning a set of values (14.13, 43.86, 43.98) indicating a clear similarity when considering the MBC-AC metric distribution, but less so for the alternative two distributions. Both models, one with a small-world (WS) structure and the other scale-free (BA), are regarded to generate graphs with different characteristics, however these results suggest a degree of similarity when using the MBC and AC metrics.

For the same metrics, the suite of infrastructure networks have also been analysed and plotted against the single standard deviation ellipses of the graph models for context and comparison (Fig. 4). For all three metric distributions, the infrastructure networks exhibit a tendency to lie in or near the standard deviation ellipse for the hierarchical graphs. Of the infrastructure networks examined, the river networks exhibit values closest to the graphs with a hierarchical organisation, with the rail networks also showing a likeness to the hierarchical models, especially for the AC-CB (Fig. 4b) and MBC-CB (Fig. 4c) distributions. The energy networks are shown to return values throughout the three distributions between those expected of a tree network and those of a random network. The values, however, are more suggestive of a hierarchical structure, with values most similar to the HR and HR+ models. Similarly, the road networks exhibit metric characteristics which are most like those of the HR and HR+ models, again suggesting they have a hierarchical structure. The air networks, conversely, exhibit a different set of characteristics, with the AC-MBC distribution being similar to the hierarchical graphs, while appearing as outliers for the AC-CB and MBC-CB distributions and not lying close to any of the graph model or other infrastructure networks analysed. This could be a result of these networks not being constrained by geography, with no limit on the number of connections a single node can have, resulting in highly disproportionate node degrees in comparison to other networks and not captured by the employed models.

The greater robustness of the non-hierarchical graph models when compared to the hierarchical graph models is shown (Fig. 5a), where nodes are removed at random sequentially (one after the other) (see Sect. 2.4 for method details). The non-hierarchical models fail following the removal, on average, of 94% of the nodes, whereas the mean for the hierarchical models is 76%, failing 19% quicker. The results from both targeted failure mechanisms (node degree and node betweenness centrality) show thy have a similar impact (Fig. 5b, c), with in both scenarios the hierarchical models failing on average after 54% of nodes have been removed and the non-hierarchical models once 80% of nodes have been removed. Through all failure methods the HC graph model exhibits a different behaviour to the other hierarchical models, failing 18% slower for the random strategy and 48% slower for the targeted strategies. This greater robustness to perturbations results in the HC graph model appearing just as robust as the non-hierarchical models, suggesting it possess a hierarchical structure yet behaves more like the non-hierarchical models.

The behaviour of the graphs generated by each graph model when exposed to the three failure models (Figs. 6, 7 and 8) indicates that the non-hierarchical models (plots (a), (b), (c) and (d)) fragment into multiple components (y-axis) much later than the hierarchical models. Failure for non-hierarchical models generally doesn’t occur until around 50% of the nodes have been removed (where the x-axis shows the % of nodes removed, from 0 to 100), irrespective of the failure model. The behaviour of the random models (plots (a) and (b)) exhibit a similar behaviour to all failure models with regard to when they start to fragment, though the number of components they then fragment into is much higher for the two targeted methods, degree and betweenness (Figs. 7 and 8), increases from 20 and 40 to ~ 140 and ~ 210 for degree and betweenness failure methods respectively. The behaviour of the other two non-hierarchical models, WS and BA (plots (c) and (d)), shows a more pronounced change, with the graphs not only starting to fragment earlier to the targeted methods, but also fragmenting into more components, from a maximum around 140 for the random failure model to 270 and 350 respectively for the two targeted models.

It is clear that the hierarchical models, plots (e), (f), (g) and (h), are more vulnerable to failures than the non-hierarchical models, as indicated by the number of components increasing much earlier when exposed to any of the three failure models. The tree model (plot (h)) starts to fragment after < 5% of nodes have been removed, with the peak in the number of components appearing after ~40% and ~10% of nodes have been removed for the random and targeted failure models respectively. The tree model graphs also fail much quicker with no components remaining left in the graphs quicker than any of the other models analysed. The hierarchical HR/HR+ models exhibit a similar behaviour with these also fragmenting as soon as a few nodes are removed, though are more robust to the failure models with the peak for the number of components being later (45–55% and 15–25% for the random targeted failure models) and for graphs remaining with some components for longer.

Of significance is the behaviour exhibited by the HC graph model (plot (g)), which exhibits a very different behaviour to the other hierarchical models. For the random failure model the HC graphs fragment differently, with all but one simulation for the model showing it to be more robust with fewer components forming and no large increase as seen in the other models. However, for the targeted failure models the graphs instead fragment immediately into a large number of components, but then unlike all the other models they then don’t fail quickly and instead appear to be robust to further failures with these not causing further fragmentation of the graphs. After reaching a peak in the number of components the HC graphs don’t fail at least until a further 50% of the nodes have been removed, whereas in the other hierarchical models this value is much closer to 20%.

The infrastructure networks are more robust to the random perturbation method (Fig. 9a) than the targeted methods, node degree and node betweenness centrality (Fig. 9b, c). Across all infrastructure sectors, for the random method the networks fail once 63% <> 78% of nodes have been removed, compared to 38% <> 62% for the targeted methods. In the random method this sees a limited variation between the robustness of the different networks, with the river networks being the least robust, failing after 63% of nodes have been removed, with the mean across the 8 infrastructure sets being 71.1%. In contrast the air networks were the least robust when the targeted methods were applied, failing after 38% of nodes had been removed, with the next worst performing being the river networks, which failed after an average of 49% of nodes had been removed. The most robust infrastructure was the road networks (national and regional), returning a value of 57.6%, also similar to the rail networks (national and regional), 55.4%.

As with the graph models, we can also analyse not just how quickly the infrastructure networks failed, but also how the structure, with regard to the number of components, changed as the networks were perturbed. The behaviour of each infrastructure network is shown across the three failure models (Figs. 10, 11, 12), once again highlighting a greater vulnerability to the targeted failure models than the random failure model. Most of the infrastructure networks exhibit a peak in the number of components around 30.3–49.0% for the random failure model (Fig. 10), though the air networks (plot (a)) exhibit a peak much earlier, after 17.0% of nodes of have been removed. These same networks then however remain connected and do not completely fail until 79.6% of nodes have been removed, whereas the other infrastructure networks fail after 57.6–76.3% of nodes have been removed. This earlier peak in the number of components is also found for the targeted failure methods, degree (Fig. 11) and betweenness (Fig. 12) suggesting a greater vulnerability for failures in the flight networks. The ability of the air network to not fail completely, however, and continue to have some connected components until a greater proportion of nodes have been removed than in the other infrastructure networks, indicates a similar behaviour (and hence structure) to the HC graph model. The network fragments into communities, but these then are individually more resilient to failures than the network as a whole.

All infrastructure networks, with the exception of the air networks, exhibit a behaviour closer to the hierarchical models, and in particular, the HR+ model. For the random failure model the peak number of components across the air networks occurs on averages when 39.8% of nodes have been removed, compared to 46.9% for the HR+ and 84.7% for the WS/BA models. With the targeted failure models this peak shifts to the left occurring after 26.0% of nodes have been removed, compared to 21.5% and 63.5% for the HR+ and BA/WS models respectively. This much greater similarity to the hierarchical graph models reflects the results given by the metric approach, highlighting once again the presence of a hierarchical structure in infrastructure networks.