Graph limits and planted partitions from the perspective of probability and statistics

PJ Wolfe, Royal Society Research Fellow (UCL)
May 5 2014 - 4:30pm
Event type: 
PACM Colloquium
Fine 214

The theory of dense graph limits has emerged as a well established tool in modern combinatorics, with close connections to applied probability and ergodic theory. In this talk we answer a probabilist's question first posed by Aldous and subsequently pursued by Kallenberg: given a single observation of a large network generated by a graph limit function (graphon) subject to bond percolation, how much information can we recover about the data-generating model? Results come by way of blockmodels, which generalize the ideas underlying the planted partition problem in theoretical computer science, as well as the community detection problem in applications of network clustering to the social and biological sciences. These results describe the natural completion of the space of such models, and significantly broaden their applicability in practice. See (with D Choi) and (with SC Olhede) for related results and applications.