Subsampling Large Graphs and Invariance in Networks

=========================================================================
                    Joint  ISOM/MATH/CSE/CSS Seminar
=========================================================================

Speaker:        Prof. Peter Orbanz
                Department of Statistics
                Columbia University

Title:          "Subsampling Large Graphs and Invariance in Networks"

Date:           Tuesday, 10 November 2015

Time:           4:30pm - 5:30pm

Venue:          Lecture Theater F (near lifts no. 25/26), HKUST

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 will show how
the choice of algorithm defines a notion of distributional invariance.
There is an algorithm for which this invariance is precisely
exchangeability; in this case, the appropriate statistical models are
so-called W-random graphs, or graphon, models. However, the invariance
changes drastically when seemingly minor modifications are made to the
subsampler; I will give a concrete example. I will also discuss the
problem of estimating properties of a distribution on large graphs from a
single large graph, and how it relates to subsampling.