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.
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.
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