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.