Correlation Decay Method for Decision, Optimization, and Inference in Large-Scale Networks
Abstract
Many inference and decision problems on networks involve solving hard algorithmic problems on graphs. Even when the underlying problem admits a polynomial time algorithm, such an algorithm can be impractical simply because of the sheer size of the underlying network, as many technological, communication, and natural networks may easily be of the order of millions or even billions of nodes. Thus one often has to resort to faster distributed (local) algorithms, which can be run in parallel on the underlying networks, providing the required time and computation effort scales. The correlation decay property, which can be established for a broad class of networks exhibiting random topology, random costs, or randomized decisions, is a tool that provides a rigorous justification for the validity of such local algorithms. In this tutorial we illustrate algorithmic methods based on the correlation decay property on several examples. Starting with the PageRank algorithm for search and navigation on the Internet, we will proceed to applications of the correlation decay method to problems in wireless communication, combinatorial optimization problems on graphs, and, finally, to the problem of network learning—a problem in the machine learning field.
This publication has no references to display.
Your Access Options
-
Login Options
Purchase Options
Save for laterOther Options
Token AccessClaim access using a tokenRestore guest accessApplies for purchases made as a guest
