"Stochastic Block Models are a Discrete Surface Tension"

A paper of mine that was published in advanced access in spring 2019 has finally received its final journal coordinates, so I am blogging about it now (even though it is old news). Here are some details.

  

Title: Stochastic Block Models are a Discrete Surface Tension

Authors: Zachary M. Boyd, Mason A. Porter, and Andrea L. Bertozzi 

Abstract: Networks, which represent agents and interactions between them, arise in myriad applications throughout the sciences, engineering, and even the humanities. To understand large-scale structure in a network, a common task is to cluster a network’s nodes into sets called “communities,” such that there are dense connections within communities but sparse connections between them. A popular and statistically principled method to perform such clustering is to use a family of generative models known as stochastic block models (SBMs). In this paper, we show that maximum-likelihood estimation in an SBM is a network analog of a well-known continuum surface-tension problem that arises from an application in metallurgy. To illustrate the utility of this relationship, we implement network analogs of three surface-tension algorithms, with which we successfully recover planted community structure in synthetic networks and which yield fascinating insights on empirical networks that we construct from hyperspectral videos.