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

点击翻译按钮获取中文摘要

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.