BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Edge-exchangeable graphs\, sparsity\, and power laws - Diana Cai (
 University of Chicago)
DTSTART:20160727T110000Z
DTEND:20160727T113000Z
UID:TALK66859@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:Many popular network models rely on the assumption of (vertex)
  exchangeability\, in which the distribution of the graph is invariant to 
 relabelings of the vertices. However\, the Aldous-Hoover theorem guarantee
 s that these graphs are dense or empty with probability one\, whereas many
  real-world graphs are sparse. We present an alternative notion of exchang
 eability for random graphs\, which we call edge exchangeability\, in which
  the distribution of a graph sequence is invariant to the order of the edg
 es. We characterize the class of edge exchangeable models with a paintbox 
 construction\, and we demonstrate that edge-exchangeable models\, unlike m
 odels that are traditionally vertex exchangeable\, can exhibit sparsity an
 d power laws. To do so\, we outline a general framework for graph generati
 ve models\; by contrast to the pioneering work of Caron and Fox (2014)\, m
 odels within our framework are stationary across steps of the graph sequen
 ce. In particular\, our model grows the graph by instantiating more latent
  atoms of a single random measure as the dataset size increases\, rather t
 han adding new atoms to the measure.<br><br>Joint work with Trevor Campbel
 l and Tamara Broderick.<br><br>
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR