InfoCoBuild

The Power of Locality for Network Algorithms

By Jennifer Chayes. Given the massive size of most networks of interest, conventional network algorithms - which typically scale as polynomials in the network size - are woefully inadequate in practice. In the first part of this talk, we consider a host of questions which are either explicitly local or can be approximated by local questions: pagerank, coverage, diffusion, determining the most influential nodes. We show how to use locality to deliver much more efficient algorithms (quasilinear or even sublinear in the network size), though sometimes at the expense of a degradation in the approximation relative to optimal algorithms. In the second part of this talk, we consider another aspect of locality, namely the question of local data access. Many large networks are encoded locally, e.g., with adjacency lists. How does the nature of the data access impact the efficiency of algorithms? Surprisingly, we show that small differences in data access can lead to very large differences in efficiency and approximability of network algorithms. As an example, we consider a covering problem which arises naturally for recruiters on social networks, and show how small differences between the information on neighbors in LinkedIn and Facebook lead to large differences in their usefulness to recruiters.

The Power of Locality for Network Algorithms


Related Links
The Machine That Changed the World
This is a 1992 documentary series on the history of electronic digital computers, from the dawn of the computer in the 1800s to the early 1990s.
Interdisciplinarity in the Age of Networks
Learn about models and techniques used to describe networks, processes to study networks, algorithms and methods developed to indirectly infer network structure from measured data which cut across many disciplinary boundaries.
How to Think like a Computer
With a thoroughly entertaining walk through the history of computing, Jake Nadal makes clear the mechanisms of computing.