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.