AF: Small: Approximation Algorithms and Topological Graph Theory

AF：小：近似算法和拓扑图论

• 批准号: 1423230
• 负责人: Yusu Wang
• 金额: $ 41.6万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423230&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Algorithms; Topological

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.

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