AF: Small: Approximation Algorithms and Topological Graph Theory

从科学和工程到金融和商业，大型而复杂的相互关联的系统在现代世界中已变得无处不在。在许多情况下，这种系统的结构是由相互作用的实体组成的网络模拟的。这种建模范式可以用于研究过多的自然对象和现象，如网络、各种网络--社会、交通、通信、系统发育--金融交易等。因此，大型和复杂网络的分析对社会来说是一项日益重要的任务。然而，从这些对象的分析中获得潜在的好处给计算科学带来了巨大的新挑战。尽管几十年来，相互关联的结构的统计分析一直是密集研究的主题，但目前的许多方法对于现代数据集来说是不够的。在高层次上，这种不足主要有两个原因。第一，网络分析的一个关键任务是发现有用的结构。也就是说，找到一个揭示有用信息的网络表示法。例如，在研究社交网络时，了解用户之间的友谊集合中是否出现特定模式可能会很有用。不幸的是，记录大量数据的能力日益增强，催生了前所未有的网络规模。因此，最初为发现较小网络中的结构而设计的方法，需要大量的计算资源才能在这些场景中发挥作用。其次，在网络中发现了一些有用的结构后，通常希望通过进一步的计算来利用它。例如，给定一个具有特定拓扑结构的运输网络，人们可能希望设计利用这种结构的运输方法。由于当代网络呈现出越来越高的复杂性的结构，在现实世界的数据集中执行这样的计算已经变得非常困难。现有的许多网络结构挖掘方法只适用于中等复杂程度的情况，因此不适用，本课题研究发现和利用大规模、大复杂性网络结构的新方法。研究工作将集中在利用所谓的逼近算法理论的思想为这两类问题设计新的算法。这些算法的目标是允许少量的误差，以换取显著更好的计算性能。关于这类算法的现有工作表明，这是克服上述网络规模和复杂性障碍的一个有希望的方向。该项目的更广泛影响包括研究生培训和开发新的研究生课程。

Large and complex interconnected systems have become ubiquitous in the modern world, from science and engineering, to finance and commerce. In many scenarios, the structure of such systems is modeled by networks of interacting entities. This modeling paradigm can be used when studying a plethora of natural objects and phenomena, such as the web, networks of all kinds - social, transportation, communication, phylogenetic - financial transactions, and so on. The analysis of large and complex networks is therefore a task of increasing importance to society. However, reaping the potential benefits from the analysis of these objects poses great new challenges for computational sciences. Even though the statistical analysis of interconnected structures has been the subject of intense study for several decades, many of the current methods are inadequate for modern data sets. At the high level, there are two main reasons for this inadequacy. First, a key task in the analysis of networks is the discovery of useful structure. That is, finding a network representation that reveals useful information. For example, when studying a social network, it can be useful to know whether specific patterns occur in the sets of friendships between users. Unfortunately, the increasing ability to record large amounts of data has given rise to networks of unprecedented size. As a consequence, methods that were originally designed for discovering structures in smaller networks, require prohibitively large amounts of computational resources to be useful in these scenarios. Second, having discovered some useful structure in a network, it is often desirable to exploit it through further computations. For example, given a transportation network with a certain topology, one might want to design shipping methods that take advantage of this structure. Performing such computations has become exceedingly intractable in real-world data sets due to the fact that contemporary networks exhibit structure of increasingly high complexity. Many current methods for exploiting network structure are only applicable to cases of moderate complexity, and are therefore inapplicable.This project investigates new methods for discovering and exploiting structure in networks of large size, and large complexity. The research effort will focus on designing new algorithms for these two classes of problems using ideas from the so-called theory of approximation algorithms. These are algorithms that aim to allow a small amount of error, in exchange for significantly better computational performance. Existing work on this type of algorithm suggests that this is a promising direction for overcoming the barriers of network size and complexity outlined above. Broader impacts of the project include graduate training and the development of a new graduate course.