Dynamic sparse graphs with overlapping communities

1. Problem Statement

The paper addresses the challenge of dynamic community detection in sparse, scale-free networks where nodes can belong to multiple overlapping communities that evolve over time.

• Limitations of Existing Models:
  • Static vs. Dynamic: Most existing models are static, failing to capture the emergence, merging, and dissolution of communities over time.
  • Sparsity and Power-Law: Traditional Stochastic Block Models (SBMs) and their dynamic extensions often assume exchangeable random graphs, which theoretically implies either dense or empty graphs. They struggle to model real-world networks that are sparse (edges scale sub-quadratically with nodes) and exhibit heavy-tailed (power-law) degree distributions.
  • Hard vs. Mixed Membership: Many dynamic models enforce "hard" clustering (nodes belong to exactly one group), whereas real-world entities often have mixed memberships (overlapping communities).
  • Node Dynamics: Many models assume a fixed set of nodes, whereas real networks often see nodes entering or exiting the system.

The authors aim to develop a model that simultaneously handles:

1. Dynamic connectivity (nodes/edges appearing/disappearing).
2. Dynamic mixed membership (overlapping communities).
3. Sparsity and power-law degree distributions.
4. Interpretability and uncertainty quantification.

2. Methodology: The dynSNetOC Model

The authors propose dynSNetOC (Dynamic Sparse Network with Overlapping Communities), a Bayesian nonparametric model.

Core Construction

The model is built upon Completely Random Measures (CRMs) coupled with a Latent Markov Process.

• Graph Representation as a Point Process:
  Instead of an adjacency matrix, the graph is modeled as an exchangeable random measure on the plane. Nodes are embedded at locations $\theta_i \in \mathbb{R}^+$, and edges are generated via a Poisson process conditioned on latent node weights.
• Overlapping Communities via Compound CRMs:
  The model uses a vector of CRMs $(W^{(t)}_1, \dots, W^{(t)}_p)$ for $p$ communities.
  • The weight of node $i$ in community $k$ at time $t$ is factorized as $w^{(t)}_{ik} = w_{i0} \beta^{(t)}_{ki}$.
  • $w_{i0}$ represents the base sociability (degree correction) of the node.
  • $\beta^{(t)}_{ki}$ represents the time-varying affiliation score of node $i$ to community $k$.
  • The weights are drawn from a Compound Generalized Gamma Process (CGGP), which ensures the resulting graph exhibits sparsity and power-law degree distributions.
• Temporal Evolution (Latent Markov Process):
  To model the evolution of community memberships, the affiliation scores $\beta^{(t)}_{ki}$ evolve stochastically.
  • The evolution is driven by augmentation variables $\gamma^{(t)}_{ki}$.
  • The transition follows a Markov structure where the distribution of $\beta^{(t+1)}$ depends on $\beta^{(t)}$ through $\gamma^{(t)}$.
  • A parameter $\psi$ controls the strength of temporal correlation (smoothness of evolution).
• Generative Process:
  1. Sample base weights $w_{i0}$ from a Generalized Gamma Process (GGP).
  2. Sample affiliation scores $\beta^{(t)}_{ki}$ evolving via the Markov process.
  3. Generate edges $n^{(t)}_{ij}$ from a Poisson distribution with rate proportional to the sum of products of community weights: $\lambda_{ij} = \sum_{k=1}^p w^{(t)}_{ik} w^{(t)}_{jk}$.

Asymptotic Properties

The authors establish theoretical results proving that:

• Sparsity: By choosing the GGP parameter $\sigma \in (0, 1)$, the number of edges $E$ scales as $O(N^{2/(1+\sigma)})$, ensuring the graph is sparse.
• Power-Law: The degree distribution follows a power law with exponent $1+\sigma$ for large degrees, matching real-world network characteristics.

Inference

Exact Bayesian inference is computationally intractable due to the infinite activity of the CRM. The authors propose an approximate inference procedure:

• Approximation: They use the exponentially tilted BFRY (etBFRY) distribution as a finite-dimensional approximation for the base weights $w_{i0}$, which converges to the GGP as the truncation level increases.
• Algorithm: They employ Hamiltonian Monte Carlo (HMC) via the NUTS sampler (implemented in NumPyro) to sample from the approximate posterior distribution of the parameters and hyperparameters.

3. Key Contributions

1. Novel Model: Introduction of the first Bayesian nonparametric model that unifies dynamic overlapping communities, sparsity, and power-law degree distributions in a single framework.
2. Theoretical Guarantees: Proof of asymptotic sparsity and power-law degree distribution properties for the proposed dynamic graph process.
3. Scalable Inference: Development of a tractable approximate inference algorithm using etBFRY and HMC, avoiding the computational bottlenecks of infinite-dimensional CRMs.
4. Dynamic Node Sets: The model naturally accommodates nodes entering and leaving the network, unlike many fixed-node dynamic models.

4. Experimental Results

The model was validated on both synthetic and real-world data.

Synthetic Data

• Validation: The model successfully recovered ground-truth community memberships and sociability weights.
• Fit: The posterior predictive degree distribution closely matched the true power-law distribution, with 95% credible intervals covering the empirical data.

Real-World Data: Reuters Terrorist Dataset

The model was applied to a network of word co-occurrences from news articles following the 9/11 attacks (6 weeks).

• Community Evolution: The model identified evolving themes such as "9/11 Attack," "Afghanistan," "Security," "Political Response," and "Anthrax."
• Dynamic Insights:
  • It captured the semantic shift of the "Attack" community from the initial WTC event to the subsequent invasion of Afghanistan.
  • It tracked the emergence of the "Anthrax" community (appearing in Week 4) and its interaction with "Security."
  • It revealed mixed memberships (e.g., words like "war" and "Bush" shifting between "Political" and "Attack" communities over time).
• Comparisons:
  • vs. Static SNetOC: The static model failed to capture temporal evolution, merging distinct phases into a single static view.
  • vs. Weekly SNetOC: Running the static model independently per week failed to track the continuity of community themes.
  • vs. dynSBM (Dynamic Stochastic Block Model): Failed to capture sparsity and power-law distributions, resulting in poor fit and uninterpretable communities.
  • vs. dMMSB (Dynamic Mixed Membership SBM): Failed to detect meaningful community structures in sparse data, effectively collapsing into a single community based on node degree.

5. Significance

This work represents a significant advancement in statistical network modeling by bridging the gap between theoretical graph limits (sparsity/power-laws) and practical dynamic analysis (overlapping, evolving communities).

• Interpretability: It provides a flexible, interpretable framework for understanding how complex systems (social, biological, technological) reorganize over time.
• Robustness: It overcomes the "dense graph" limitation of classical exchangeable models, making it applicable to the vast majority of real-world sparse networks.
• Future Impact: The framework opens avenues for modeling covariates, estimating the number of communities dynamically, and applying these techniques to large-scale temporal networks in fields ranging from epidemiology to financial market analysis.