Details of Grant 

EPSRC Reference:	EP/T004878/1
Title:	Multilayer Algorithmics to Leverage Graph Structure (MultilayerALGS)
Principal Investigator:	Meeks, Dr K
Other Investigators:	Lee, Professor DP Guo, Dr H Enright, Dr J Wong, Dr M
Researcher Co-Investigators:	Dr F Skerman
Project Partners:	University of Bergen
Department:	School of Computing Science
Organisation:	University of Glasgow
Scheme:	Standard Research
Starts:	01 July 2020	Ends:	30 June 2025	Value (£):	765,538
EPSRC Research Topic Classifications:	Fundamentals of Computing Logic & Combinatorics
EPSRC Industrial Sector Classifications:	Information Technologies
Related Grants:
Panel History:	Panel Date Panel Name Outcome 10 Jul 2019 EPSRC ICT Prioritisation Panel July 2019 Announced
Summary on Grant Application Form
Graphs are popular as a structure for modelling systems of connections in the real world, and graph theory has taken a major role in the wider field of algorithmics and computational complexity. Many of the algorithmic problems we might wish to solve on graphs (e.g. extracting useful information, or identifying optimal modifications) are intractable in general, but there has been significant progress in recent decades in our understanding of how mathematical structure in graphs can be exploited to design efficient algorithms. However, many real-world datasets are not sufficiently highly structured for this approach to be effective. In this project we aim to address this issue by exploiting the fact that many real-world systems exhibit qualitatively different types of connections, driven by fundamentally different processes. For example, online friendships are not geographically constrained, and you may have online friends that you have never met in person. In contrast, the set of friends you see regularly in person is subject to geographical factors, and may revolve around common activities or meeting places. These two types of links are different in the processes that produce them, in the structure of the graph they form, and in their role in answering different questions. We call a system like this, with multiple different types of links, a multilayer system, and we can model it with a multilayer graph in which entities represented by nodes are linked by several different classes of links, or 'edges'. Such multilayer systems arise in a huge range of different real-world applications, and the crucial observation for our work is that the structure of each individual layer is typically much easier to understand and to describe mathematically than that of the entire system. Our strategy is therefore to develop methods that allow us to use our understanding of the structure of the individual layers to answer questions about the entire system within an acceptable amount of time. Our theoretical results will produce dichotomy meta-theorems which allow us to identify precisely, for a wide range of problems involving systems of this kind, the structural properties of individual layers that will allow us to solve the problems efficiently. Central to the development of these new algorithmic results will be a better understanding of the structure of real-world multilayer systems, so we will also develop new ways to model and simulate multilayer graphs. Our work will include a variety of case studies on real-world data, including human contact information from online social networks, medical statistics, and ecological and epidemiological disease transmission data.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.gla.ac.uk