Locality via global ties: Stability of the 2-core against misspecification

For many random graph models, the analysis of a related birth process suggests local sampling algorithms for the size of, e.g., the giant connected component, the k-core, the size and probability of an epidemic outbreak, etc. In this talk, I consider the question of when these algorithms are robust against misspecification of the graph model, for the special case of the 2-core.

As we will see, for locally converging graphs with bounded average degrees, under a weak notion of expansion, a local sampling algorithm provides robust estimates for the size of both the 2-core and its largest component, even if the graph under consideration is not locally tree like. Our method involves a two-step sprinkling argument. In the first step, we use sprinkling to establish the existence of a non-empty 2-core inside the giant, while in the second, we use this non-empty 2-core as seed for a second sprinkling argument to establish that the giant contains a linear sized 2-core.

This work is joint with my student Geng Zhao.