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

在过去的二十年里，大量的网络或图表出现在社会的结构中。例如，网络以社交网络的形式出现，例如Facebook上的人，分享网络，例如Twitter，计算机网络，例如互联网的路由器，以及电力系统。了解这些真实世界网络的结构是一项基本的科学挑战。这种结构的一个重要方面是“社区”的存在，或网络中对象的紧密结合的集合，其中有大量的连接;例子包括社交网络中的一大群共同朋友，或共享网络中的回声室。分析社区结构以及其他结构特征的常用技术是使用随机游走。在这种技术中，人们想象一个粒子在图中随机行走，简单地从一个对象移动到另一个对象，每一步都遵循一个随机连接。尽管这种技术很简单，但它构成了最先进的社区检测和图形采样方法的基础;然而，尽管关于随机游走有丰富而深刻的数学理论，但人们对这种技术的成功缺乏理解。特别是，目前的随机游走理论基本上使用的措施“瓶颈”（称为电导），并表明，随机游走是有效的，当没有瓶颈。但有压倒性的经验证据表明，现实世界的图包含瓶颈，但随机游走是有效的分析它们。这项研究的主要目的是对这种现象进行科学调查，希望找到正确的数学工具来解释这种行为。考虑到大规模网络在现代社会中的核心作用，这类研究在科学研究中发挥着基础性作用。在早期的工作中，人们已经认识到，经典的电导概念过于粗糙，无法理解真实世界的图形。本研究的目的是设计更丰富的电导措施来研究随机游走的行为，设计可证明的鲁棒算法来近似这些措施，并证明这些措施的相关性，在图采样的算法问题。调查的出发点是一个“截断”的电导概念，忽略了小集，在离散数学文献中引入研究凸体的体积。研究人员认为，这是对现实世界图上随机游动的更有用的表征。这导致了一些研究挑战。第一个挑战是设计有效的算法，近似这些更丰富的电导措施。第二个挑战是要证明现有的经验主义是利用这些其他的电导措施，以获得性能比以前的理论预测。第三个挑战是在真实世界的图表上对这些措施进行详细的研究，以便从经验上为理论奠定基础。这项研究的副产品之一将是对现实世界图形的实际结构有更深入的了解，这可能会激发更好的模型。这项研究的主要成果将以定理和算法的形式出现，以及描述它们的论文，这些论文描述了更丰富的电导测量对网络上运行的算法行为的影响。研究人员还计划发布软件来计算或近似新的电导措施proposed.This奖项反映了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.