AF: Small: Collaborative Research: An Investigation of Richer Conductance Measures for Real-World Graphs

在过去的二十年里，庞大的网络或图形出现在社会的结构中。例如，网络以社交网络（如Facebook上的人）、共享网络（如Twitter）、计算机网络（如Internet的路由器）和电力系统的形式出现。理解这些现实世界网络的结构是一项基本的科学挑战。这种结构的一个重要方面是“社区”的存在，或者是网络中紧密结合的对象集合，其中有大量的连接；例如，社交网络中的一大群共同的朋友，或者共享网络中的回音室。分析社区结构以及其他结构特征的常用技术是使用随机漫步。在这种技术中，人们想象一个粒子在图中随机行走，通过在每一步跟随随机连接从一个物体移动到另一个物体。尽管这项技术很简单，但它构成了最先进的社区检测和图形采样方法的基础；然而，尽管有丰富而深入的随机漫步数学理论，人们对这种技术的成功却缺乏理解。特别是，目前关于随机漫步的理论基本上使用了“瓶颈”（称为电导）的度量，并表明当没有瓶颈时随机漫步是有效的。但有压倒性的经验证据表明，现实世界的图形包含瓶颈，而随机漫步对于分析它们是有效的。这项研究的主要目的是对这种现象进行科学调查，希望找到正确的数学工具来解释这种行为。鉴于大规模网络在现代社会中发挥的核心作用，此类研究在科学研究中发挥着基础作用。在早期的工作中已经认识到，经典的电导概念对于理解现实世界的图形来说太粗糙了。本研究的目的是设计更丰富的电导度量来研究随机游走的行为，设计可证明的鲁棒算法来近似这些度量，并证明这些度量与图采样算法问题的相关性。研究的起点是一个忽略小集的“截断”电导概念，该概念在离散数学文献中引入，用于研究凸体的体积。研究人员认为，这是一个更有用的表征随机漫步在现实世界的图表。这给研究带来了许多挑战。第一个挑战是设计有效的算法来近似这些更丰富的电导测量。第二个挑战是证明现有的经验启发法正在利用这些其他电导测量，以获得比先前理论预测的更好的性能。第三个挑战是在现实世界的图表上对这些测量进行详细的研究，以便在经验上建立理论基础。这项研究的副产品之一将是对现实世界图形的实际结构有更深入的了解，这可能会激发更好的模型。这项研究的主要成果将以定理和算法以及描述它们的论文的形式出现，这些定理和算法描述了更丰富的电导测量对网络上运行的算法行为的影响。研究人员还计划发布软件来计算或近似提出的新电导测量。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Over the past two decades, massive networks or graphs appear in the very fabric of society. For example, networks appear in the form of social networks such as people on Facebook, sharing networks such as Twitter, computer networks such as the routers of the Internet, and power systems. Understanding the structure of these real-world networks is a fundamental scientific challenge. A significant aspect to this structure is the existence of "communities", or tightly knit collections of objects in the network with a large number of connections within them; examples iwould include a large group of mutual friends in a social networks, or an echo-chamber in a sharing network. A common technique to analyze community structure, as well as other structural features, is the use of random walks. In this technique, one imagines a particle that randomly walks in the graph by simply moving from object to object by following a random connection at each step. Despite the simplicity of this technique, it forms the foundation for state-of-the-art community-detection and graph-sampling methods; however, although there is a rich and deep mathematical theory on random walks, there is a lack of understanding for the success of this technique. In particular, the current theory on random walks essentially uses measures of "bottlenecks" (called conductance), and shows that random walks are effective when there are no bottlenecks. But there is overwhelming empirical evidence that real-world graphs contain bottlenecks, yet random walks are effective for analyzing them. The main aim of this research is a scientific investigation of this phenomenon, with the hope of finding the right mathematical tools to explain this behavior. Given the central role that massive networks play in modern society, such studies play a fundamental role in scientific research.It has been recognized in earlier work that the classic notion of conductance is too crude a lens to understand real-world graphs. The aim of this research is to design richer conductance measures to study the behavior of random walks, design provably robust algorithms to approximate these measures, and demonstrate the relevance of these measures for algorithmic problems in graph sampling. The starting point for the investigation is a "truncated" notion of conductance that ignores small sets, introduced in the discrete math literature to study volumes of convex bodies. The investigators believe this to be a more useful characterization of random walks on real-world graphs. This leads to a number of research challenges. The first challenge is to design efficient algorithms that approximate these richer conductance measures. The second challenge is to prove that existing empirical heuristics are exploiting these other conductance measures, to get performance better than that predicted by previous theory. The third challenge is to perform a detailed study of these measures on real-world graphs in order to empirically ground the theory. One of the by-products of this research will be a greater insight into the actual structure of real-world graphs, and this will likely inspire better models. The primary outcomes from this research will be in the form of theorems and algorithms, as well as papers describing them, that characterize the impact of richer conductance measures on the behavior of algorithms run on networks. The investigators also plan to release software to compute or approximate the new conductance measures proposed.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.