PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1810.01778v1stat.MLcs.LGcs.SI

TL;DR

The paper addresses how to build interpretable random graph models with realistic sparsity, degree distributions, and latent community structure. It develops inhomogeneous random graph models and an overlapping-community extension, with a link function enabling scalable posterior inference. The models produce the targeted asymptotic behaviors and fit empirical degree distributions while recovering latent communities on real-world networks.

  • Problem

    The paper seeks graph models that simultaneously represent sparsity, scale-free or truncated power-law degree behavior, and latent community structure with interpretable parameters.

    Source: §1 · pp. 1–2

  • Method

    The paper builds on inhomogeneous random graphs, extends them to overlapping communities, and uses a specific link probability for scalable posterior inference.

    Source: §1 · p. 2, §4.1 · p. 6, §5.1 · p. 7

  • Results

    The models are sparse, support scale-free degree distributions with exponent greater than 2 or power-law distributions with exponential cut-off, and fit empirical degree distributions while recovering latent communities.

    Source: §1 · p. 2, §3.2 · p. 3, §3.3.1 · p. 5

  • Takeaways & Limitations

    The framework provides a flexible statistical approach for modeling degree heterogeneity and overlapping community structure in real-world networks.

    Source: §1 · p. 2, §4.1 · p. 6, §7.1 · p. 10

    The construction lacks projectivity, and its inhomogeneous random graph formulation has an asymptotically constant mean number of triangles.

    Source: §6 · pp. 8–9

Abstract

from arXiv · show

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.

1 Introduction

The paper develops interpretable graph models designed to capture sparsity, scale-free degree behavior, and overlapping latent communities. It targets realistic asymptotic properties while supporting analysis of real-world network structure.

1 Introduction

  • The framework is motivated by applications including link prediction and uncovering interpretable latent structure in networks.Source: §1 · p. 1
  • The models aim to combine interpretable parameters with realistic asymptotic properties, especially sparsity and scale-freeness.These properties are motivated by the study of real-world networks and their degree distributions.Source: §1 · pp. 1–2
  • Latent community affiliation is modeled as influencing the probability that two vertices connect, allowing overlapping structure to be represented.Source: §1 · p. 2
  • The paper develops sparse graph models with overlapping communities and well-specified asymptotic degree distributions.Depending on parameters, the models are either scale-free with exponent η > 2 or have power-law degree distributions with exponential cut-off.Source: §1 · p. 2

2 Sparse and scale-free networks

This section formalizes sparsity and scale-freeness for random graph sequences, establishing the definitions used in the paper’s results. It characterizes scale-free degree distributions through slowly varying functions and relates the definition to power-law behavior.

  • The paper defines sparsity for a graph sequence by requiring E(|E_n|)/n^2 → 0 as the number of vertices n grows.Source: §2 · p. 2
  • A graph sequence is defined as scale-free with exponent η when its asymptotic degree counts satisfy a condition involving a slowly varying function ℓ and η > 1.Source: §2 · p. 2
  • Slowly varying functions change more slowly than any power of x, providing the scale-invariance underlying the paper’s definition of scale-free networks.Source: §2 · p. 2
  • When ℓ(k) is constant, the asymptotic degree distribution behaves as a pure power law for large k; logarithmic and iterated-logarithmic choices also satisfy the scale-invariance condition.Source: §2 · p. 3
  • The paper notes that its scale-free definition is slightly more restrictive than van der Hofstad’s Definition 1.4, while being sufficient to imply it through regular-variation properties.Source: §2 · p. 3

3 Rank-1 inhomogeneous random graphs

The rank-1 inhomogeneous random graph model uses node weights in its link probability, yielding sparse graphs with degree distributions governed by the weight distribution. Different weight choices produce either scale-free power laws or power laws with exponential cut-offs.

3.1 Definition

  • The model connects nodes through a link probability based on independently sampled positive weights, where larger weights represent greater node sociability.The weights control degree heterogeneity and the likelihood that a node connects to others.Source: §3.1 · p. 3

3.2 Sparsity and scale-free properties

  • The resulting graph sequence is sparse, and its asymptotic degree distribution is a mixed Poisson distribution with mixing distribution F.These properties follow from results attributed to Bollobás et al. [2007].Source: §3.2 · p. 3
  • Regularly varying weight distributions yield scale-free graphs under the stated degree-count asymptotics.The result requires a regularly varying distribution with density tail f(w) ∼ ℓ(w)w^−η for η > 1.Source: §3.2 · p. 4

3.3.1 Scale-free graph with power-law degree distribution

  • Inverse gamma weights produce scale-free graphs with power-law degree distributions having arbitrary index α + 1 > 2.The shape parameter α tunes the power-law index, while α and β also relate to graph sparsity.Source: §3.3.1 · pp. 4–5, Figure 1 · p. 5

3.3.2 Non scale-free graph with power-law degree distribution with exponential cut-off

  • Generalized inverse Gaussian weights produce non-scale-free graphs whose degree distributions have power-law form k^(ν−1)e^(−τk) with an exponential cut-off.The parameters ν, a, and b tune the power-law index, cut-off, and sparsity; Figure 1 compares empirical and theoretical distributions and edge counts.Source: §3.3.2 · pp. 5–6, Figure 1 · p. 5

4 Extension to Latent Overlapping Communities

The paper extends the inhomogeneous random graph model to latent overlapping communities while preserving tractable asymptotic analysis of sparsity and degree distributions.

4.1 Definition

  • The rank-c model adds latent overlapping community structure to an inhomogeneous random graph and studies its sparsity, scale-freeness, and asymptotic degree distribution.Source: §4.1 · p. 6
  • The model assumes iid sociability weights with finite mean and iid community-affiliation vectors with finite moments.Source: §4.1 · p. 6
  • Each node has an overall sociability parameter w_i and community-specific affiliation parameters v_iq.The sociability parameter provides degree correction, while v_iq measures affiliation with community q.Source: §4.1 · p. 6
  • Theorem 4.1 characterizes the number of edges and the asymptotic counts of vertices with each degree under the rank-c link probability.Source: §4.1 · pp. 6–7
  • Let H be the distribution of U = Pc; additionally, F is absolutely continuous with pdf f satisfying f(w) ∼ℓ(w)w−η as w →∞, with η > 1.The conditions also require E(U η−1+ϵ) < ∞ for some ϵ > 0 and locally bounded slowly varying ℓ.Source: §4.1 · p. 7
  • The paper considers Dirichlet-distributed community affiliations, with all concentration parameters positive.Source: §4.1 · p. 7

5 Posterior inference

Posterior inference uses auxiliary truncated-Poisson variables and MCMC updates, with the link function enabling computation that scales with nodes and observed edges rather than all node pairs.

5.1 Posterior inference for the rank-1 NR

  • Rank-1 inference introduces truncated-Poisson auxiliary variables for observed edges and uses MCMC with HMC updates, auxiliary-variable resampling, and Metropolis-Hastings hyperparameter updates.Source: §5.1 · p. 7
  • For the rank-1 model, collapsing non-edge terms reduces log-joint-density and gradient computation to O(n + |E_n|).This avoids the O(n^2) cost reported for other rank-1 inhomogeneous random-graph link functions.Source: §5.1 · p. 7

5.2 Posterior inference for the rank-c NR

  • The rank-c model extends the same strategy with multivariate truncated-Poisson variables for community-specific contributions.Source: §5.2 · p. 8
  • Rank-c log-joint-density and gradient computation takes O(cn + c|E_n|) time, followed by HMC sampling of w and V, auxiliary-variable resampling, and Metropolis-Hastings updates.Source: §5.2 · p. 8

6 Discussion

The models combine sparsity, scale-free behavior, interpretable community structure, and scalable inference, but sacrifice projectivity and have a limitation concerning triangle formation.

  • The models capture sparsity, scale-freeness with exponent η > 2, and latent community structure.Source: §6 · p. 8
  • The construction is non-projective because the link probability is normalized by s_n.The discussion contrasts this with projective graphon-based models, which produce dense graphs with probability one.Source: §6 · p. 8
  • Unlike preferential-attachment models, the model is finitely exchangeable for each n, so node ordering need not be known for inference.Source: §6 · p. 8
  • Figure 2 reports 95% credible intervals for predictive degree distributions and posterior samples of hyperparameters for IG-NR and GIG-NR.The caption gives true values α = 1.5 and β = 3.0 for IG-NR, and ν = −0.5, a = 0.1, and b = 3.0 for GIG-NR.Source: Figure 2 · p. 9
  • The mean number of triangles in inhomogeneous random graphs converges to a constant as n grows, which may be undesirable for real-world networks.Latent community structure may mitigate this effect for reasonable n.Source: §6 · p. 9

7 Experiments

Experiments show that the proposed models fit degree distributions on synthetic and real-world graphs, while the community extension retains competitive degree and community recovery performance.

7.1 Experiments with the rank-1 models

  • IG and GIG recover synthetic hyperparameters and provide good posterior-predictive fits to empirical degree distributions.Source: §7.1 · p. 9
  • On three real-world networks, IG and GIG fit degree distributions with exponents greater than 2, whereas GGP fails to capture their shape.Source: §7.1 · p. 10, Figure 3 · p. 10

7.2 Experiments with latent overlapping communities

  • The overlapping-community experiments evaluate IG-NR, GIG-NR, CGGP, and MMSB on polblogs and a DBLP subsample using degree-distribution and clustering measures.Source: §7.2 · pp. 10–11, Table 1 · p. 11, Table 2 · p. 11
  • GIG-NR and CGGP fit polblogs well, while IG-NR and GIG-NR fit DBLP; IG-NR and GIG-NR outperform other methods on DBLP community classification.Source: §7.2 · p. 11, Figure 4 · p. 12
  • MMSB fails to capture both degree distributions and community structures in the presence of large degree heterogeneity.Source: §7.2 · p. 11

A On scale-free networks

The paper contrasts finite-sample tests of scale-freeness with asymptotic behavior and develops its models within the inhomogeneous random graph framework.

A On scale-free networks

B Background material on regular variation

C Background on inhomogeneous random graph models

D Proof of Theorem 3.1 and Theorem 3.2

The proofs embed the rank-1 models into the general inhomogeneous random graph framework and then invoke its graphical-kernel and degree-distribution results.

E Proof of Theorem 4.1

The supplementary material extends the IRG proof to rank-c models, describes posterior samplers, and reports sparsity-preserving degree behavior and community recovery.

E Proof of Theorem 4.1

F.1 Posterior inference for the rank-1 model

  • Rank-1 inference samples weights with HMC, latent counts with truncated Poisson sampling, and hyperparameters with Metropolis-Hastings.Source: §F.1 · p. 20

F.2 Posterior inference for the rank−c model

  • Rank-c inference additionally samples community affiliations with HMC and uses a transformation that makes Dirichlet variables unconstrained with an efficiently computed Jacobian.Source: §F.2 · pp. 21–22

G.1 Empirical degree distributions and number of edges for rank−c model

G.2 Discovered community structures

  • IG, GIG, and CGGP discover reasonable communities, whereas MMSB completely fails to discover them under large degree heterogeneity.Source: §G.2 · p. 23, Figure 7 · p. 24

Related papers

Loading 1810.01778v1…