From Graphon to Graphex: Models and Estimators for Sparse Networks using Exchangeable Random Measures

Duration: 38 mins 59 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/2289921/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Roy, D (University of Toronto) Tuesday 26th July 2016 - 14:30 to 15:00


Created:	2016-07-28 15:22
Collection:	Theoretical Foundations for Statistical Network Analysis
Publisher:	Isaac Newton Institute
Copyright:	Roy, D
Language:	eng (English)


Abstract:	A major challenge for Bayesian network analysis is that we lack general nonparametric models of sparse graphs. To meet this challenge, we introduce and study the general class of random graphs defined by the exchangeability of their real-valued vertex labels, an idea inspired by a model due to Caron and Fox. A straightforward adaptation of a result by Kallenberg yields a representation theorem: every such random graph is characterized by three (potentially random) components: a nonnegative real I, an integrable function S : R+ to R+, and a symmetric measurable function W: R+^2 to [0,1] that satisfies several weak integrability conditions. We call the triple (I,S,W) a graphex, in analogy to graphons, which characterize the (dense) exchangeable graphs on the naturals. I will present some results about the structure and consistent estimation of these random graphs. This is joint work with Victor Veitch.

Abstract:

A major challenge for Bayesian network analysis is that we lack general nonparametric models of sparse graphs. To meet this challenge, we introduce and study the general class of random graphs defined by the exchangeability of their real-valued vertex labels, an idea inspired by a model due to Caron and Fox. A straightforward adaptation of a result by Kallenberg yields a representation theorem: every such random graph is characterized by three (potentially random) components: a nonnegative real I, an integrable function S : R+ to R+, and a symmetric measurable function W: R+^2 to [0,1] that satisfies several weak integrability conditions. We call the triple (I,S,W) a graphex, in analogy to graphons, which characterize the (dense) exchangeable graphs on the naturals. I will present some results about the structure and consistent estimation of these random graphs. This is joint work with Victor Veitch.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.94 Mbits/sec	567.71 MB	View	Download
WebM	640x360	619.94 kbits/sec	177.08 MB	View	Download
iPod Video	480x270	522.31 kbits/sec	149.13 MB	View	Download
MP3	44100 Hz	249.8 kbits/sec	71.39 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)