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

Juho Lee, Lancelot F. James, Seungjin Choi, François Caron

Introduction

Modeling large-scale real-world networks requires balancing mathematical flexibility with computational tractability. Most empirical networks exhibit three fundamental properties: sparsity, a scale-free degree distribution, and overlapping community structures. This paper introduces a novel Bayesian framework that simultaneously captures these features while maintaining linear scalability with respect to the number of edges.

The Challenge of Real-World Networks

Statistical models for networks often face a trade-off. Traditional "graphon-based" Bayesian models frequently result in dense graphs, where the number of edges grows quadratically with the number of nodes—a property rarely seen in real-world data. Conversely, models that successfully incorporate sparsity often struggle to represent the specific power-law exponents ($\eta > 2$) common in social and biological networks, or they become computationally prohibitive for networks exceeding a few thousand nodes.

Methodology: The Rank-c Norros-Reittu Framework

The authors propose an extension of the Norros-Reittu (NR) inhomogeneous random graph model. The core innovation lies in the choice of the link function:

$$p_{ij} = 1 - \exp\left(-\frac{w_i w_j}{s_n}\right)$$

Unlike standard logistic links, this exponential form allows the likelihood terms for non-existent edges to be collapsed into a single summation. This reduces the computational complexity of posterior inference from $O(n^2)$ to $O(n + |E|)$, where $|E|$ is the number of edges.

To incorporate community structure, the model is extended to a "Rank-c" version. Each node $i$ is characterized by a sociability parameter $w_i$ and a latent affiliation vector $v_i \in \mathbb{R}^c_+$, representing its membership across $c$ overlapping communities.

Scalability and Structural Flexibility

A key strength of this model is its ability to adapt to different global network shapes through the choice of priors for node weights. The authors utilize Inverse Gamma (IG) priors to generate pure power-law distributions and Generalized Inverse Gaussian (GIG) priors for power-laws with exponential cut-offs.

Degree distribution flexibility and linear edge growth. The left panels show how varying parameters allows the model to capture diverse power-law behaviors. The right panels demonstrate that the number of edges scales linearly with the number of nodes, confirming the model's sparsity.

As shown in the figure above, the model maintains sparsity (linear edge growth) across a wide range of parameter settings while providing the flexibility to fit various degree distribution tails.

Empirical Performance

The model was validated against five real-world datasets, including the internet router network (124,651 nodes) and the polblogs dataset.

  • Degree Distribution Fit: The IG-NR and GIG-NR models significantly outperformed existing methods like the Generalized Gamma Process (GGP) in fitting the heavy-tailed distributions of the cond-mat and Enron datasets.
  • Community Recovery: On the polblogs dataset, the model achieved a clustering accuracy of 94.28%. This success is attributed to "degree correction"—the model's ability to distinguish between a node's inherent sociability and its community-driven connections.
  • Scalability: By leveraging Hamiltonian Monte Carlo (HMC) and the NR computational shortcut, the authors performed inference on the 120k-node internet dataset, a scale that is typically prohibitive for many latent-variable Bayesian graph models.

Conclusion

By combining the computational efficiency of the Norros-Reittu link function with the structural flexibility of GIG priors and Rank-c latent vectors, this framework provides a robust tool for analyzing massive, complex networks. While the model is non-projective, this is a justified trade-off for achieving the realistic combination of sparsity and scale-freeness required for modern network science.

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\'as et al. [2007], we show that i) the class of models is sparse and ii) depending on the choice of the parameters, the model is either scale-free, with power-law exponent greater than 2, or with an asymptotic degree distribution which is power-law with exponential cut-off. We propose an extension of the model that can accommodate an overlapping community structure. Scalable posterior inference can be performed due to the specific choice of the link probability. We present experiments on five different real-world networks with up to 100,000 nodes and edges, showing that the model can provide a good fit to the degree distribution and recovers well the latent community structure.
BibTeX
@inproceedings{lee2019bayesian,
  author = {Juho Lee and Lancelot F. James and Seungjin Choi and François 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