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

AF：小：协作研究：对现实世界图更丰富的电导测量的研究

基本信息

批准号：
1909528
负责人：
David Gleich
金额：
$ 25万
依托单位：
Purdue University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909528&HistoricalAwards=false
关键词：
AF Small Collaborative Research Investigation

项目摘要

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.

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

项目成果

期刊论文数量（16）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple

DOI：
10.1137/22m1502008
发表时间：
2023-07
期刊：
SIAM J. Matrix Anal. Appl.
影响因子：
0
作者：
Charles Colley;Huda Nassar;D. Gleich
通讯作者：
Charles Colley;Huda Nassar;D. Gleich

Classes of preferential attachment and triangle preferential attachment models with power-law spectra

具有幂律谱的优先附着类别和三角形优先附着模型

DOI：
10.1093/comnet/cnz040
发表时间：
2020
期刊：
Journal of Complex Networks
影响因子：
2.1
作者：
Eikmeier, Nicole;Gleich, David F
通讯作者：
Gleich, David F

Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs

DOI：
10.1145/3394486.3403238
发表时间：
2020-02
期刊：
Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
影响因子：
0
作者：
Nate Veldt;Anthony Wirth;D. Gleich
通讯作者：
Nate Veldt;Anthony Wirth;D. Gleich

Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering

用于半监督学习和局部图聚类的强局部 p-norm-cut 算法