Skip to yearly menu bar Skip to main content


Poster
in
Workshop: Structured Probabilistic Inference and Generative Modeling

The Pairwise Prony Algorithm: Efficient Inference of Stochastic Block Models with Prescribed Subgraph Densities

Lee M Gunderson · Gecia Bravo-Hermsdorff · Peter Orbanz

Keywords: [ efficient inference on graphs ] [ stochastic block models (SBMs) ] [ matrix pencil method ] [ graphons ]


Abstract:

We present an elegant and flexible algorithm that provides the parameters of the simplest stochastic block model (SBM) for a given set of prescribed subgraph densities, from which one can sample networks with negligible computational overhead. The method generalizes the classical method of Prony to the pairwise data of networks. The class of inferred models are at the intersection of exponential random graph models (ERGMs), which are characterized in terms of maximum entropy, and of exchangeable random graphs (i.e., graphons). We show that the required subgraph densities can be efficiently computed for both dense and sparse networks, and provide an implementation of our algorithm in python. Our method provides standardized null models for statistical analysis of network data, including for the challenging case of a single observed graph.

Chat is not available.