Analysis of graph algorithms in random and semi-random generative models

Summary

We will study the use of techniques from linear algebra and from convex optimization to solve graph problems where the graph is sampled from a random or a semi-random generative model. A "semi-random" generative model is one intermediate between worst-case and average-case, where the graph is generated with a combination of random choices and adversarial choices.

We will see how to apply spectral (i.e. linear-algebraic) techniques to find a planted clique or planted independent set in a random graph, and to discover communities in the "stochastic block model" of random networks. We will then see how to apply semidefinite programming (a convex optimization methodology that generalizes both linear programming and certain spectral methods) to both problems, and study how it performs in semi-random variants of the planted clique model and of the stochastic block model.

Lecture plan:

  1. The planted clique problem, properties of random matrices, and a spectral algorithm to find planted cliques
  2. The stochastic block model and spectral algorithms for community detection
  3. Semidefinite programming, its application to planted clique and to stochastic block model. Reasoning about robustness in the semi-random setting.

Readings

We will refer to notes written for this course, and in particular to Handout 0 and to Handouts 4 to 10.

Problem Sets