Multilayer Algorithmics to Leverage Graph Structure (MultilayerALGS)

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.

Because this project includes both theoretical and application-focused activities, we plan a wide range of impact, both intrinsic to the research and via targeted impact activities. We outline our potential impact in three parts: academic, non-academic practice, and general public.

Academic:
The theoretical side of this project will have impact in theoretical computing, graph theory, and network modelling. This will be mediated by academic publications, presentations at meetings and seminars, and training of postgraduate students. We will target a variety of publication venues to suit different project outputs, submitting larger and more general results (e.g. dichotomy meta-theorems) to prestigious generalist venues (e.g. FOCS or STOC), with more specific parameterised complexity or graph theoretic results going to field-specific venues (e.g. IPEC or WG). Following these conference publications, we plan to submit corresponding journal manuscripts to appropriate journals (e.g. Algorithmica, JCSS, JACM). Impact on more distant academic fields, including network epidemiology, applied statistics and the social sciences, will be brought about as a part of the case studies, during which we will publish and present in appropriate application venues (e.g. Epidemics, Annals of Applied Statistics, Social Networks). We intend to include several graduate students in topics related to this project: both Edinburgh and Glasgow have existing CDTs and DTPs to support graduate students in mathematics and computing, particularly around data science, and we will propose studentships to calls from those CDTs and DTPs. In addition, we plan to organise a workshop on multi-layer algorithmics in the final year of the project, with a variety of researchers in both algorithmics and network science invited. We hope that this workshop, and resulting collaborations, will accelerate the project's academic impact.

Non-Academic Practice:
Our application-area case studies will ultimately have impact for practitioners outside academia. Improved modelling of agricultural networks arising from our network epidemiology case study will allow policy-makers in the area of animal health to model infectious diseases more accurately, ultimately benefiting the agriculture industry. We plan to mediate this impact through existing relationships Co-I Enright has formed in her previous 6 years of experience in modelling in agriculture, and existing related BBSRC project (BB/R009309/1) in cooperation with the aquaculture industry in Scotland. Our health statistics case study aims to develop and provide proof-of-concept for new methods for exploiting health data both to inform public policy on large-scale health interventions and to improve individual diagnosis and treatment within the field of precision medicine. In both domains our tools have the potential to improve outcomes for individual patients as well as reducing the overall cost of treatment for the NHS. The co-operation of two domain experts will facilitate the dissemination of our results to clinical practitioners. The case study on online social networks will provide new tools and insights for policy-makers with an interest in communities and inequality, ultimately benefiting individuals who face issues such as social exclusion online. A number of such practitioners participated in a workshop organised by co-I Wong in 2018, and these contacts will provide a first route for disseminating our results.

General Public:
As well as ultimately benefiting from the impact on non-academic practitioners mentioned above, the general public will benefit more directly from our planned outreach activities. Our three main methods of public knowledge exchange will be with school pupils (focused on Maths Week Scotland), with lay adults as part of Pint of Science events in Edinburgh and Glasgow, and via a Twitter microblog which has already been started and will be maintained throughout the project (@multilayerAlgs).