Subsampling, symmetry and averaging in networks

Duration: 34 mins 46 secs

Share this media item:

Embed this media item:

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

Choose size:

About this item

Available Formats

About this item

Description:	Orbanz, P (Columbia University) Monday 11th July 2016 - 14:30 to 15:00


Created:	2016-07-18 17:20
Collection:	Theoretical Foundations for Statistical Network Analysis
Publisher:	Isaac Newton Institute
Copyright:	Orbanz, P
Language:	eng (English)


Abstract:	Consider a very large graph---say, the link graph of a large social network. Now invent a randomized algorithm that extracts a smaller subgraph. If we use the subgraph as sample data and perform statistical analysis on this sample, what can we learn about the underlying network? Clearly, that should depend on the subsampling algorithm. I show how the choice of algorithm defines a notion of (1) distributional invariance and (2) of averaging within a single large graph. Under suitable conditions, the resulting averages satisfy a law of large numbers, such that statistical inference from a single sample graph is indeed possible. From this algorithmic point of view, graphon models arise from a specific choice of sampling algorithm, various known pathologies of these models are explained as a selection bias.

Abstract:

Consider a very large graph---say, the link graph of a large social network. Now invent a randomized algorithm that extracts a smaller subgraph. If we use the subgraph as sample data and perform statistical analysis on this sample, what can we learn about the underlying network? Clearly, that should depend on the subsampling algorithm. I show how the choice of algorithm defines a notion of (1) distributional invariance and (2) of averaging within a single large graph. Under suitable conditions, the resulting averages satisfy a law of large numbers, such that statistical inference from a single sample graph is indeed possible. From this algorithmic point of view, graphon models arise from a specific choice of sampling algorithm, various known pathologies of these models are explained as a selection bias.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.94 Mbits/sec	506.25 MB	View	Download
WebM	640x360	481.42 kbits/sec	122.65 MB	View	Download
iPod Video	480x270	522.05 kbits/sec	132.94 MB	View	Download
MP3	44100 Hz	249.79 kbits/sec	63.67 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)