Algorithms for Graphs and Communication Networks: A Model-Bridging Approach

图和通信网络的算法：模型桥接方法

• 批准号: RGPIN-2022-04518
• 负责人: King, Valerie
• 金额: $ 2.99万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749842
• 关键词: Algorithms; Graphs; Communication; Networks; Model

Graphs are widely used to model connections between entities. Massive graphs like the web graph or a model of the human brain may contain billions of nodes, making them hard to analyze. This puts a burden on computing resources like processing time, memory, and bandwidth in networks. One approach to reduce time is to recognize that graph problems are typically ongoing, with incremental changes over time. Dynamic graph algorithms reuse information from prior computations so that solutions can be updated as the graph changes. In the streaming model, information about the graph is processed as it streams through the processor using a space much smaller than what would be needed to keep the whole graph. In a parallel system, processors each have partial information about the graph and work simultaneously; they communicate via either a shared memory or via links between processors. A distributed communications network may itself be regarded as a graph over which the nodes know only their neighbors and collectively communicate in order to route information or solve problems. In a large network such as the web, there is also the possibility that some nodes are faulty or self-interested. In this type of scenario, coordination and collective decision-making among the nodes become important and a challenge, even when all nodes link directly to each other. Much recent progress has resulted from a cross-pollination of ideas arising from these models. In particular, the various measures of efficiency for the different models appear to be related: the update time for a dynamic algorithm, the amount of communication needed for a distributed algorithm, the work done by a parallel algorithm and the space needed for a streaming algorithm. Furthermore the methodologies for solving problems in these models are related as well, and insight gained for one model gives insight into another. We have seen that these new insights can lead us not only to better performance in these models, but also faster algorithms for classical sequential computers. Our goal is to use a model-bridging perspective to design more efficient graph algorithms and prove limits on what is possible. Fast, efficient algorithms use less energy and may be able to quickly provide real time solutions to complex problems. Collective decision-making which is fair and effective and does not incur high energy costs is increasingly important in the world of digital currency and influential reputation systems.

图被广泛用于实体之间的连接建模。像网络图或人脑模型这样的大规模图形可能包含数十亿个节点，这使得它们很难分析。这给网络中的处理时间、内存和带宽等计算资源带来了负担。减少时间的一种方法是认识到图形问题通常是持续的，随着时间的推移会发生增量变化。动态图算法重用来自先前计算的信息，因此可以在图变化时更新解决方案。在流模型中，有关图的信息在流经处理器时进行处理，使用的空间比保存整个图所需的空间要小得多。在并行系统中，每个处理器都有关于图的部分信息，并且同时工作；它们通过共享内存或处理器之间的链接进行通信。分布式通信网络本身可以看作是一个图，在这个图上节点只知道它们的邻居，并且为了路由信息或解决问题而集体通信。在像web这样的大型网络中，也存在一些节点故障或自利的可能性。在这种类型的场景中，节点之间的协调和集体决策变得非常重要，也是一种挑战，即使所有节点都直接相互连接。最近的许多进展都是由这些模型产生的思想的交叉授粉造成的。特别是，不同模型的各种效率度量似乎是相关的：动态算法的更新时间，分布式算法所需的通信量，并行算法完成的工作以及流算法所需的空间。此外，在这些模型中解决问题的方法也是相关的，从一个模型中获得的洞察力可以提供对另一个模型的洞察力。我们已经看到，这些新的见解不仅可以使我们在这些模型中获得更好的性能，还可以使经典顺序计算机的算法更快。我们的目标是使用模型桥接的视角来设计更有效的图算法，并证明可能的极限。快速、高效的算法使用更少的能量，可能能够快速地为复杂问题提供实时解决方案。在数字货币和有影响力的声誉系统的世界里，公平有效、不产生高额能源成本的集体决策变得越来越重要。