Combinatorial Optimization, Spin Models, and the Geometry of Sparse Random Graphs

网络和图是无处不在的数学模型，用于描述重要的系统（社会网络、交通网络和生物系统等）。网络由一定数量的对象（通常称为“节点”或“顶点”）组成，这些对象由不同重要性的链接（“边”和它们的“权重”）连接起来。众所周知，分析网络数据具有挑战性。一个重要的任务是将顶点分组到子组中，这样每个子组都是高度连接的，并且任何两个子组只有松散的互连。即使一个人只是试图识别两个子群（称为最小对分问题），通常也没有有效的算法来划分大型图的节点。当考虑到图可能具有随机结构时，情况就发生了变化。事实上，对于许多合理的图概率模型，似乎存在求解最小二分问题的有效算法。这个项目将发展我们对这些概率模型的基本理解，并将研究有效的算法来处理它们。本项目重点研究了稀疏随机图的各种模型，其中最简单的是平均度有界的Erdos-Renyi（独立边）随机图。许多统计推理任务可以通过适当定义的组合优化问题来解决。例如，最小等分问题要求找到顶点集的一个平衡分区，使分区上的边数最小化。这些优化问题与底层图上的某些吉布斯度量相关联，从中恢复优化器作为基态。统计物理学家推测，这些吉布斯测度（对于随机图）与适当定义的自旋玻璃模型的吉布斯测度是渐近等价的。本课题旨在建立这种牢固的联系，并利用它来研究大型随机图的结构。最近也有人提出，同样问题的半定规划松弛可以通过其他吉布斯测度（带矢量自旋）来研究。研究这些自旋模型将提高我们对解决这些任务的有效算法的理解。

Networks and graphs are ubiquitous mathematical models to describe important systems (social networks, transportation networks, and biological systems, among others). A network is comprised of a certain number of objects (normally referred to as 'nodes' or 'vertices') connected by links of various importance ('edges' and their 'weights'). Analyzing network data is notoriously challenging. An important task is to group the vertices into subgroups such that each subgroup is highly connected, and any two subgroups have only loose interconnections. Even if one is only trying to identify merely two subgroups (known as the min-bisection problem), no efficient algorithm is known to partition the nodes of large graphs in general. The situation changes when one considers that the graphs might have a random structure. Indeed, for many reasonable probabilistic models on graphs, there appear to be efficient algorithms to solve the min-bisection problem. This project will develop our fundamental understanding of these probabilistic models and will study efficient algorithms to treat them.The project focuses on various models of sparse random graphs, the simplest being the Erdos-Renyi (independent edges) random graph, with bounded average degree. Many statistical inference tasks can be addressed by suitably defined combinatorial optimization problems. For instance, the min-bisection problem requires to find a balanced partition of the vertex set that minimizes the number of edges across the partition. These optimization problems are associated to certain Gibbs measures on the underlying graph, from which the optimizers are recovered as ground states. Statistical physicists conjectured that these Gibbs measures are asymptotically equivalent (for random graphs) to Gibbs measures of suitably defined spin glass models. This project aims at establishing this connection on a firm basis and exploiting it to study the structure of large random graphs. It has also recently been suggested that semidefinite-programming relaxations for the same problems can be studied through other Gibbs measures (with vector spins). Studying these spin models will improve our understanding of efficient algorithms for solving these tasks.