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 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.

arXiv commentto appear in Journal of Nonlinear Science

References in corpus (35)

• Finding and evaluating community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Epidemic processes in complex networks
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Temporal Networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• The performance of modularity maximization in practical contexts
• A roadmap for the computation of persistent homology
• Social Structure of Facebook Networks
• Modern temporal network theory: A colloquium
• The ground truth about metadata and community detection in networks
• Analysis of the structure of complex networks at different resolution levels
• Structure and inference in annotated networks
• Structure and dynamics of core-periphery networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Pseudo-likelihood methods for community detection in large sparse networks
• Role Discovery in Networks
• A network analysis of committees in the United States House of Representatives
• Network Analysis of Particles and Grains
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Estimating the number of communities in a network
• Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection
• Efficient method for estimating the number of communities in a network
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Block Models and Personalized PageRank
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Unsupervised Classification in Hyperspectral Imagery with Nonlocal Total Variation and Primal-Dual Hybrid Gradient Algorithm
• Community detection in networks via nonlinear modularity eigenvectors