Title: Stochastic Block Models are a Discrete Surface Tension,
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 bridge, 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 from the field of
hyperspectral video segmentation.