Sublinear algorithms in social networks via core-periphery decomposition

Large real-world social and information networks have a number of known beyond-worst-case structural characteristics that can support the design of fast algorithms. One of these characteristics is a heavy-tailed degree distribution: there is a significant number of very high-degree nodes. Another related structural characteristic is a core-periphery structure: large networks often have a large, well-connected core, and many small isolated periphery components.

In this talk I will discuss our line of research developing practical sublinear algorithms for large networks, based on the core-periphery structure and the degree distribution. Our data structure, which maintains a hierarchical core-periphery decomposition, requires only sublinear preprocessing and can help accelerate a variety of tasks such as node sampling, triangle sampling, and shortest path computations. I will also include some theoretical justifications for the good performance, highlighting the fine balance between theory and empirical results in this domain.

Based on joint works with Sabyasachi Basu, Talya Eden, Dimitris Fotakis, Nadia Koshima, Joel Oren, Tim Rieder, and C. Seshadhri