A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure.

Juho Lee, Lancelot F. James, Seungjin Choi, Francois Caron

Abstract: We consider a non-projective class of inhomogeneous random graph models with interpretable parameters and a number of interesting asymptotic properties. Using the results of Bollobás et al. (2007), we show that the proposed framework can simultaneously capture sparsity, overlapping communities, and diverse degree distributions.

Introduction

Real-world networks, ranging from social media interactions to biological protein networks, typically exhibit two fundamental properties: sparsity and heavy-tailed degree distributions. Sparsity implies that as the number of nodes ($n$) increases, the number of edges grows much slower than $n^2$. Heavy-tailed distributions, often following a power law, indicate that while most nodes have few connections, a small number of "hubs" are highly connected.

Traditional statistical models often struggle to capture both properties while remaining computationally scalable and interpretable. This paper introduces a flexible Bayesian framework that addresses these challenges, allowing for overlapping community structures and degree distributions that include power laws with exponential cut-offs.

Methodology

The model is built upon rank-1 inhomogeneous random graphs, specifically the Norros-Reittu model. In this setup, each node $i$ is assigned a "sociability" parameter $w_i$, and the probability of an edge between nodes $i$ and $j$ is determined by the product $w_i w_j$.

Flexible Priors and Sparsity

To achieve flexible degree distributions, the authors employ two types of priors for the sociability weights:

  • Inverse Gamma (IG) Prior: Generates scale-free graphs with a power-law exponent $\eta > 2$.
  • Generalized Inverse Gaussian (GIG) Prior: Allows for a power law with an exponential cut-off, providing a more accurate fit for networks where the power law drops off at very high degrees.
Figure 1: Empirical degree distributions and edge growth for varying model parameters. The top row illustrates the effect of IG parameters ($\alpha, \beta$), while the bottom row shows GIG parameters ($\nu, a$).

Community Structure and Scalable Inference

To incorporate overlapping communities, the model is extended to a rank-$c$ setup. Each node is represented by a latent vector $v_i$ indicating its affiliation strength to $c$ different communities. Nodes with similar community affiliations are more likely to connect.

A key contribution of this work is a scalable Markov chain Monte Carlo (MCMC) inference algorithm. By utilizing a specific link function and auxiliary Poisson variables, the authors collapse calculations for non-edges, reducing computational complexity from $O(n^2)$ to $O(n + |Edges|)$. This allows the model to scale linearly with the size of the network.

Empirical Results

The model was evaluated on synthetic data and several real-world datasets, including the cond-mat co-authorship network, Enron emails, and the internet router map.

Degree Distribution Fit and Parameter Recovery

The IG and GIG models provided a significantly better fit to empirical degree distributions compared to existing benchmarks. Posterior predictive checks demonstrate that the model accurately captures the distribution of the data while maintaining interpretable parameter estimates.

Figure 3: Posterior predictive checks for degree distribution (data vs. prediction) and histograms showing parameter recovery for $\alpha, \beta, \nu, a, b$.

Community Detection

On the polblogs dataset, the model achieved approximately 94% accuracy in community identification, outperforming the Mixed Membership Stochastic Blockmodel (MMSB). This success is attributed to the model's ability to account for degree heterogeneity—recognizing that some nodes are naturally more active than others regardless of their community membership.

Conclusion and Future Work

This Bayesian framework provides a robust and scalable approach to modeling large-scale networks with complex structures. While the model is non-projective, this trade-off is necessary to achieve the desired sparsity and scale-free properties. Future research may explore adaptations for directed graphs or temporal networks that evolve over time.

Summary updated

Abstract

We consider a non-projective class of inhomogeneous random graph models with interpretable parameters and a number of interesting asymptotic properties. Using the results of Bollobás et al. (2007),...
BibTeX
@inproceedings{lee2019bayesian,
  author = {Juho Lee and Lancelot F. James and Seungjin Choi and Francois Caron},
  title = {{A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure.}},
  booktitle = {AISTATS},
  year = {2019},
  url = {https://openreview.net/forum?id=1wpMuE0rrkx},
}
Figure