AF: Small: Approximation Algorithms and Topological Graph Theory

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

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.