Theory and applications of higher-order network models

Lead Research Organisation: University of Strathclyde
Department Name: Mathematics and Statistics


Networks (or graphs) provide a useful modelling tool to describe very different complex systems, from brains and ecosystems to social organisations, financial markets, transportation systems, and power grids, to name a few. Since these complex systems consist of entities that interact or relate to each other, network models represent them as graphs where the components are described as vertices and the edges capture pairwise (dyadic) interactions between them. One of the main strengths of these models is in their ability to relate the structure of systems to their dynamic; for example, a communication network of a community of people may provide insights into how a new idea spreads across the members of such a community, since the network is the mean that allows the information to flow.
On the other hand, a fundamental shortcoming of current network models is their inability to appropriately capture higher-order interactions, i.e., those interactions that occur between more than two components. For example, consider three people, named A, B, and C, that collaborate together. A standard network would model this triadic interaction using three pairs, namely (A, B), (B, C), and (C, A). However, the relationship between these people would be better represented using a single interaction, (A,B,C), that standard network model cannot store. This exemplifies something that has become more and more apparent with the advent of big data and the growing evidence that these often present several instances of group-based interactions, which standard network models fail to capture.
The aim of this project is to model, describe, and apply new classes of network models that effectively capture higher-order interactions occurring in complex systems; this will in turn allow for a better understading of the behavior and dynamics of such systems.
A key reason for the limited number of higher-order network models is that data is often collected in a pairwise format: higher-order information is disregarded at the data-collection stage. However, this limitation can sometimes be overcome by using the metadata accompaining the experimental information; For example, collaborative relationships among more than two authors can be recovered by looking at the authors list of the papers they have co-authored.

The main modelling tool that will be used is simplicial complexes from algebraic topology. Simplices generalize line segments in higher-dimensional spaces and thus can be effectively used to represent many-body interactions. A simplicial complex is then just a collection of 'connected' simplices.
The theory developed will provide a theoretical framework for analytical tools that will allow to quantify the importance of components within the network, as well as to identify large-scale structures (e.g., clusters of densely connected components) in terms of higher-order interactions.
The theory will be equipped with a set of computationally efficient algorithms that will ensure wide applicability of the introduced techniques, especially for large datasets.
The developed techniques will be tested against standard network models and other available higher-order representations of networks, including tensor representations.
This studentship will contribute to understanding how to incorporate and take advantage of higher-order information in networks modelling complex systems. It will develop mathematical, statistical, and computational tools for analysis of higher-order interactions and open up novel data analytics for relational data. The wide applicability of the theory and algorithmics developed will allow testing on publicly available real-world data.


10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/T517938/1 30/09/2020 29/09/2025
2434800 Studentship EP/T517938/1 30/09/2020 30/07/2024 Stephen Adair