2018/06/30 by Zachary M. Boyd, Mason A. Porter, Andrea L. Bertozzi · 5 citations
Computer Science · Mathematics · Physics and Astronomy · #Block (permutation group theory) #Cluster (spacecraft) #Cluster analysis #Community structure #Complex Network Analysis Techniques #Construct (python library) #Generative grammar #Markov Chains and Monte Carlo Methods #Stochastic block model #Task (project management) #Theoretical and Computational Physics #cond-mat.stat-mech #cs.SI #math.ST #msc:35Q56 #msc:49M20 #msc:62H30 #msc:65K10 #msc:91C20 #msc:91D30 #msc:94C15 #nlin.AO #stat.ML #stat.TH
paper · pdf · doi:10.1007/s00332-019-09541-8
published in Journal of Nonlinear Science 30(5), 2429-2462 (Springer Science+Business Media) · to appear in Journal of Nonlinear Science
openalex created_date 2018/06/13 · arxiv created 2019/03/25 · openalex publication_date 2019/04/22 · arxiv updated 2019/05/22 · openalex updated_date 2026/08/06
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.