Edge-exchangeable graphs, sparsity, and power laws
34 mins 9 secs,
62.48 MB,
MP3
44100 Hz,
249.78 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Cai, D (University of Chicago)
Wednesday 27th July 2016 - 12:00 to 12:30 |
|---|
| Created: | 2016-07-28 15:23 |
|---|---|
| Collection: | Theoretical Foundations for Statistical Network Analysis |
| Publisher: | Isaac Newton Institute |
| Copyright: | Cai, D |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| Abstract: | 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 guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We present an alternative notion of exchangeability for random graphs, which we call edge exchangeability, in which the distribution of a graph sequence is invariant to the order of the edges. We characterize the class of edge exchangeable models with a paintbox construction, and we demonstrate that edge-exchangeable models, unlike models that are traditionally vertex exchangeable, can exhibit sparsity and power laws. To do so, we outline a general framework for graph generative models; by contrast to the pioneering work of Caron and Fox (2014), models within our framework are stationary across steps of the graph sequence. In particular, our model grows the graph by instantiating more latent atoms of a single random measure as the dataset size increases, rather than adding new atoms to the measure.
Joint work with Trevor Campbell and Tamara Broderick. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.93 Mbits/sec | 496.22 MB | View | Download | |
| WebM | 640x360 | 651.85 kbits/sec | 162.96 MB | View | Download | |
| iPod Video | 480x270 | 522.44 kbits/sec | 130.55 MB | View | Download | |
| MP3 * | 44100 Hz | 249.78 kbits/sec | 62.48 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||