Talks
Fall 2016

Distribution-Free Models of Social and Information Networks

Wednesday, September 21st, 2016 2:10 pm3:00 pm

Add to Calendar

Location: 

Calvin Lab Auditorium 

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.