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

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

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.