Abstract
Many massive empirical networks fail to partition into a small number of clusters or modules. As such, standard "global" partitioning algorithms are searching for structure that may not exist. Instead, a number of researchers have demonstrated the advantages of local clustering algorithms that find small clusters. This talk provides a statistical framework for local clustering algorithms by (i) showing how sparse and transitive Stochastic Blockmodels have small "local" clusters and (ii) illustrating that triangles in sparse and stochastic networks lead to the blessing of transitivity. This allows for fast local algorithms with statistical guarantees under a semi-parametric Stochastic Blockmodel that makes limited assumptions on the vast majority of the network.