When: February 4, 2015, 12:30 PM
Location: Researchers' Link, Discovery Building
Contact: 608-316-4401, firstname.lastname@example.org
Jordan Ellenberg speaks on Have you heard the good news about L^p graphons?
We talk a lot in this seminar about random graphs, and by this we often mean random graphs in the Erdos – Renyi sense (each edge is present or absent, independently, with probability p) or its generalization, the stochastic blockmodel (nodes come in k colors, for each pair of colors there’s a different edge probability between 0 and 1; Erdos-Renyi is the k=1 case.) In recent years, the theory of “graph limits” or “graphons” has been developed; this gives us a very nice analytic way of describing various “Erdos-Renyi-like” graphs. You might think of it as the limit of the stochastic block model as k goes to infinity.
But there’s a problem. All these models are DENSE — that is, the expected number of edges is constant*N^2, where N is the number of vertices. What’s more, the vertex degrees concentrate around a constant (in the Erdos-Renyi case) or a finite set of constants (in the stochastic blockmodel case.) Real networks we encounter are not like this. They are typically sparse (number of edges = o(N^2) or even O(N)) and degrees vary widely (e.g. according to a power law.) There are various ad hoc ways of generating graphs with these properties (e.g. preferential attachment) but no general theory of random graph models, descriptive statistics for such graphs, etc.
Then last week Henry Cohn told me about the development by him, Christian Borgs, Jennifer Chayes, and Yufei Zhao at Microsoft Research of the theory of “L^p graphons,” a more flexible model which seems very well-positioned to capture the feature of real-world large graphs.
I will give an intro to their paper and present a bunch of questions which I’ll bet nobody’s really worked on yet and which I think are important.
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.
Speaker: Jordan Ellenberg