On the 26th October, as part of the monthly Geospatial Engineering meeting, I presented an update on some of my research thus far, since beginning my PhD last September. The presentation focused on some of the more recent research I have been doing, associated with identifying a hierarchical structure in networks. Below is a summary of the work and a note on future presentations.
It is acknowledged in infrastructure literature that some infrastructures have a hierarchical structure, different from the traditional theoretic network structures. These include common models like the random model, scale-free and small-world structures. The main difference between graph structures is the distribution of node degree, the proportion of nodes which are connected to a certain number of edges. A hierarchical structure (looks like a tree) would be expected to have some sort extra organization in it, leading to an underlying hierarchical structure, such as a tree. If it can be shown that this is true and hierarchical networks can be identified, it may be shown that the structure of these are significant and thus may allow for the improvement of the resilience of such networks.
The research utilised the networkx python library, a complex network package. This allowed for the creation of the common network structures mentioned earlier, as well as for the analysis of these through an extensive collection of analysis algorithms. To create a better representation of hierarchical networks, two in-house algorithms were developed to soften he transition between random networks and the balanced tree network, an explicit hierarchical network.
The first set of analysis was performed using common graph metrics such as degree (the number of edges connected to a node) and the average shortest path across a network. A suite of graphs were created for this analysis which covered a range of sizes and complexities for all graph types. This led to the identification of a pair of metrics, which in combination, allowed hierarchical networks to be separated from the other graph structures in the analysis. (The metrics which were identified are the assortativity coefficient and the max betweenness centrality value).
The accuracy of this was confirmed through a series of statistical test, for all pair wise combinations, including chi-squared tests as well as transformed divergence tests to compare the distribution patterns of the metrics of all graph types. In the majority of cases it was shown that the distributions for the graph types did not match in many cases, and there was a significant difference between the rest and the hierarchical structures.
This shows that there is a significant difference between the structure types and thus further investigation into the significance of this, as planned, is worth while completing as there could be future implications on the resilience and design of infrastructure networks. This work will involve resilience analysis of the range of network structures so the results can be compared and the significance quantified. In the longer term this work will be applied onto real-world networks.
A similar presentation with recently completed work will be presented at the ITRC Early Career Researchers Conference at the end of November.