Linear and sublinear algorithms for graphlet sampling

In this talk we will consider the following problem, known as graphlet sampling: given an integer k ≥ 3 and a simple graph G, sample a connected induced k-vertex subgraph of G uniformly at random. We will discuss algorithms for this problem with linear and sublinear preprocessing time, as well as some recent adaptations to the semi-streaming and MPC settings.