27.09.2018 18:48 Age: 25 days
Category: Publications
By: Louis J. Dubé

Stochastic Block Model goes universal


Mesoscopic patterns learned from and imposed on a real complex network. All results are obtained on the polblog dataset, a directed network of hyperlinks between weblogs on U.S. politics, recorded shortly after the 2004 presidential election.

In the latest published contribution of Dynamica, Mesoscopic Pattern Extraction (MPE) and SBM share central stage. Under the evocative title “Universality of the SBM”, MPE is considered under the looking glass of the SBM. The Abstract tells some of the story. “MPE is the problem of finding a partition of the nodes of a complex network that maximizes some objective function. Many well-known network inference problems fall in this category, including, for instance, community detection, core-periphery identification, and imperfect graph coloring. In this paper, we show that the most popular algorithms designed to solve MPE problems can in fact be understood as special cases of the maximum likelihood formulation of the stochastic block model (SBM) or one of its direct generalizations. These equivalence relations show that the SBM is nearly universal with respect to MPE problems.”

Links to the full text and preprints are available on the Publication page.