Estimating clique composition and size distributions from sampled network data

Cliques are defined as complete graphs or subgraphs; they are the strongest form of cohesive subgroup, and are of interest in both social science and engineering contexts. In this paper we show how to efficiently estimate the distribution of clique sizes from a probability sample of nodes obtained from a graph (e.g., by independence or link-trace sampling). We introduce two types of unbiased estimators, one of which exploits labeling of sampled nodes neighbors and one of which does not require this information. This is the first work to present statistically principled design-based estimators for clique distributions in arbitrary graphs using sampled network data. We generalize our estimators to cases in which cliques are distinguished not only by size but also by node attributes, allowing us to estimate clique composition by size. Last, we compare our estimators on a variety of real-world graphs and provide suggestions for their use.