Identifying the hierarchical structure of networks – Presentation summary

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.

 

Geomatics and Water Seminar Series

Hi all,

This week saw the restart of our seminar series in conjunction with the water group from within our School. A weekly event during term time, with seminars held on Monday lunch times, sees a good turn out from staff, researchers and students from both the undergraduate and postgraduate degree programmes.

To kick-off this year we hosted Muki Haklay from UCL speaking on ‘Crowdsourced geographic information and citizen science – can we trust the data?’ With a strong turn out from all, the presentation went down well amongst those present. The presentation included many interesting and thought provoking points as well as intriguing results about the accuracy of Open Street Map compared to Ordnance Survey data.

Next week the series sticks with a geospatial engineering theme when Simon Buckley from the Centre for Integrated Petroleum Research (Bergen) will be presenting ‘Integration of close range hyperspectral imaging and terrestrial lidar for geological outcrop mapping’.

New team members

We welcome a few new members to the Geospatial Engineering group at Newcastle at the start of this new academic year. There are two more students starting their PhD’s with us and a new member of staff. More details on their roles and research interests will published as they settle into life in the department.