Local Structure and Inference in Large Random Graphs

Modern social networks now contain on the order of 100 million to 1 billion active profiles. The graph structure of these networks contains an unprecedented amount of information about the social connectivity of the world; however, contemporary algorithms used to estimate random graph models from data are computationally intractable at this scale. To address this, we turn to the graphon random graph model. Graphons are suited to modeling data with a large number of nodes, and where exchangeability of the nodes can be assumed.

Various estimation procedures for graphons exist in the literature. However, accurate estimation requires either an unbiased sample or some way to account for potential bias in the sampling scheme. We present a framework for working with small edge-induced samples of graphons. To account for the sampling bias, we first establish theory that describes the sampling distribution of these subgraphs. Building on this, we propose a procedure for undoing the sampling bias. This allows for estimation of whole-network structure from only an ego network. An interesting consequence of these results is that the mutual friend counts found on most social media platforms contain a great deal of information about the local community structure. Finally, we characterize the asymptotic behavior of a different network model, the Edge-Degeneracy exponential random graph model.