Graph limits and planted partitions from the perspective of probability and statistics
Graph limits and planted partitions from the perspective of probability and statistics
SPECIAL PACM COLLOQUIUM:听听 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.