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

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

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.