Large Random Structures and Network Flow

该项目的中心主题是研究通过网络的最佳流量，其中网络的不同方面（拓扑，边缘容量，成本）可能是随机的。本文将介绍几种不同的方法：从统计物理中对空腔方法的概率重新表述，建立网络规模增长时极限存在性的局部弱收敛，以及来自概率组合学和随机图的更多标准技术。其中一些技术还将应用于随机数据上的各种组合优化问题，检查问题的计算硬度与近最优解结构的猜想。网络流问题已经在许多不同的学科中得到了研究：电气工程、计算机科学、运筹学、交通工程、区域经济学。该提案启动了在随机网络背景下对这些问题的抽象模型进行系统的数学研究，其中随机性用于捕获非集中设计的网络的想法。数学家拥有研究非常大的系统而不做精确计算的技术（随着系统变大，精确计算变得越来越困难），这与工程师更熟悉的技术是分开的。设想的更广泛的影响是促进技术在不同研究团体之间的传播，并为设计大型网络提供额外的工具。

The central theme of the project is study of optimal flows through networks, where different aspects of the network (topology, edge-capacities, costs) may be random. Several different methodologies will be brought to bear: a probabilistic reformulation of the cavity method from statistical physics, local weak convergence for establishing existence of limits as network size grows, as well as more standard techniques from probabilistic combinatorics and random graphs. Some of these techniques will also be applied to various combinatorial optimization problems over random data, examining a conjecture relating computational hardness of problem to structure of near-optimal solutions.Network flow problems have been studied in many different disciplines: Electrical Engineering, Computer Science, Operations Research, Transportation Engineering, Regional Economics. The proposal initiates systematic mathematical study of abstracted models of these problems in the context of random networks, where randomness is used to capture the idea of networks not being centrally designed. Mathematicians have techniques for studying very large systems without doing exact calculations (which become more difficult as systems get larger) which are separate from the techniques more familiar to engineers. The broader impacts envisaged are facilitating the spread of techniques between different research communities and providing additional tools for the design of large networks.