Stochastic Block Models are a Discrete Surface Tension
This work offers a novel theoretical connection for network clustering, potentially improving methods for analyzing community structure in various applications, though it appears incremental as it adapts existing algorithms to a new context.
The paper demonstrates that maximum likelihood estimation in stochastic block models (SBMs) is analogous to a continuum surface-tension problem from metallurgy, and by implementing network versions of surface-tension algorithms, it successfully recovers planted communities in synthetic networks and provides insights on empirical networks from hyperspectral videos.
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.