Abstract
The mathematical study of social and information networks has centered around generative models for such networks (preferential attachment, the Chung-Lu random graph model, Kronecker graphs, etc.). This work proposes distribution-free models of social and information networks --- novel classes of graphs that capture all plausible such networks. Our models are motivated by triadic closure, the property that vertices with one or more mutual neighbors tend to also be neighbors; this is one of the most universal signatures of social networks. We prove structural results on the clustering properties of such graphs, and give algorithmic applications to clustering and clique-finding problems.
Includes joint work with Jacob Fox, Rishi Gupta, C. Seshadhri, Fan Wei, and Nicole Wein.