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; 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.

从科学和工程到金融和商业，大型且复杂的互连系统在现代世界中变得无处不在。在许多情况下，此类系统的结构是由交互实体网络建模的。在研究大量自然物体和现象时，可以使用这种建模范式，例如网络，各种网络 - 社交，运输，交通，沟通，系统发育 - 财务交易等。因此，大型和复杂网络的分析是对社会重要性提高的任务。但是，从对这些对象的分析中获得潜在的好处，对计算科学面临着巨大的挑战。尽管几十年来对互连结构的统计分析一直是激烈研究的主题，但许多当前的方法对于现代数据集而言不足。在高水平上，这种不足的主要原因有两个。首先，网络分析的关键任务是发现有用的结构。也就是说，找到一个揭示有用信息的网络表示。例如，在研究社交网络时，知道在用户之间的朋友集中是否发生特定模式可能会很有用。不幸的是，记录大量数据的越来越多的能力导致了空前规模的网络。结果，最初设计用于在较小网络中发现结构的方法经常需要大量的计算资源才能在这些情况下有用。其次，在网络中发现了一些有用的结构后，通常需要通过进一步的计算来利用它。例如，给定具有一定拓扑的运输网络，人们可能想设计利用这种结构的运输方法。由于当代网络的发现结构越来越高，进行此类计算在现实世界数据集中变得更加广泛地棘手。当前利用网络结构的许多当前方法仅适用于现代复杂性的情况，因此不适用。该项目调查了发现和利用大型网络和大复杂性网络中结构的新方法。研究工作将着重于使用所谓的近似算法理论中的思想为这两类问题设计新算法。这些算法旨在允许少量错误，以换取明显更好的计算性能。现有关于此类算法的工作表明，这是克服上面概述的网络大小和复杂性障碍的承诺方向。该项目的更广泛影响包括研究生培训和开发新的研究生课程。