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.