PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical clustering of temporal networks through a dynamic stochastic block model

Catherine Matias, Vincent Miele

arXiv:1506.07464v2stat.ME

TL;DR

Dynamic network clustering requires methods that handle changing memberships without losing temporal label correspondence. The paper combines an SBM with independent Markov group evolution, establishes identifiability under stable within-group connectivity, and develops inference and model-selection procedures evaluated on synthetic and contact-network data.

  • Problem

    Dynamic network clustering lacks straightforward temporal group comparisons because memberships and connectivity can vary across time, creating label-switching and identifiability challenges.

  • Method

    The paper combines an SBM for static connectivity with independent Markov chains for node-group evolution, using variational expectation maximization and ICL for inference and group-count selection.

  • Results

    The method provides identifiable parameters under stable within-group connectivity and achieves global ARI values above 0.8 in identifiable cases when group stability or connectivity separation is sufficient.

  • Takeaways & Limitations

    The framework supports temporally coherent clustering of binary and weighted dynamic networks and is applied to high-school contact and animal-interaction networks.

  • Takeaways & Limitations

    Dynamic affiliation SBM parameters are not identifiable without additional constraints, and increasing time points can sometimes reduce performance as group changes become more likely.

Abstract

from arXiv · show

Statistical node clustering in discrete time dynamic networks is an emerging field that raises many challenges. Here, we explore statistical properties and frequentist inference in a model that combines a stochastic block model (SBM) for its static part with independent Markov chains for the evolution of the nodes groups through time. We model binary data as well as weighted dynamic random graphs (with discrete or continuous edges values). Our approach, motivated by the importance of controlling for label switching issues across the different time steps, focuses on detecting groups characterized by a stable within group connectivity behavior. We study identifiability of the model parameters, propose an inference procedure based on a variational expectation maximization algorithm as well as a model selection criterion to select for the number of groups. We carefully discuss our initialization strategy which plays an important role in the method and compare our procedure with existing ones on synthetic datasets. We also illustrate our approach on dynamic contact networks, one of encounters among high school students and two others on animal interactions. An implementation of the method is available as a R package called dynsbm.

1. Introduction

The paper addresses challenges in clustering discrete-time dynamic networks by combining stochastic block models with Markovian group evolution. It emphasizes identifiable, temporally coherent groups with stable within-group connectivity while supporting varied edge types and model selection.

  • Motivation: Dynamic network clustering must account for evolving node groups and temporal label-switching issues that complicate comparisons across snapshots.The paper situates dynamic modeling as a newer area with substantial challenges and focuses on classifications that remain coherent over time.
  • Modeling approach: The model combines a stochastic block model for static connectivity with independent Markov chains governing each node’s group membership over time.This structure provides a smooth evolution of latent groups across time.
  • Identifiability: Focusing on groups with stable within-group connectivity helps ensure parameter identifiability and supports valid frequentist inference.The approach distinguishes stable connectivity behavior from unrestricted temporal variation in memberships and connectivity parameters.
  • Model scope: The framework covers binary and weighted dynamic random graphs, including sparse or dense networks and discrete or continuous edge values.This broadens the model beyond binary networks and fixed connectivity assumptions used in related approaches.
  • Inference and evaluation: The paper contributes variational expectation maximization inference, an integrated classification likelihood criterion for selecting group counts, and a detailed initialization strategy.It compares the procedure with existing methods on synthetic data and applies it to dynamic contact networks.

2. Setup and notation

The model combines time-varying stochastic block models with independent Markov chains governing latent group memberships. It addresses cross-time label switching by focusing on groups with stable within-group connectivity parameters.

  • Observation model: Networks are modeled as undirected and without self-loops, so each adjacency matrix is symmetric with an empty diagonal.
  • Model structure: Each individual’s group membership evolves as an irreducible, aperiodic stationary Markov chain, with chains iid across individuals.The transition matrix is π and the initial distribution is stationary.
  • Model structure: At each time point, conditional on latent memberships, the network follows a stochastic block model.The dynamic graphs are conditionally independent given the latent groups.
  • Observation model: The model supports weighted interactions, including Gaussian, truncated Poisson, finite-space, and zero-inflated edge distributions.The binary case is included as a special case, while weighted cases retain a parametrized family F.
  • Identifiability: The analysis therefore focuses on groups characterized by stable within-group connectivity behavior rather than only highly connected communities.This setting is presented as particularly suited to social and contact networks where individuals may change groups over time.
  • Identifiability: Allowing both memberships and connectivity parameters to vary freely over time creates label-switching and identifiability problems.Without additional constraints, groups may not be recovered consistently across time, including in dynamic affiliation SBMs.
  • Identifiability: Under the stated constraint, parameters are generically identifiable up to label switching in the binary case for sufficiently large N and in the weighted case when N ≥3.The weighted result additionally requires Assumption 1; binary-case thresholds are specified more precisely elsewhere.

3. Inference algorithm

The inference procedure uses a variational approximation to estimate dynamic SBM parameters when the latent-variable likelihood is intractable. Its Markov-chain variational structure, parameter updates, ICL model selection, and initialization are central to the algorithm.

  • Variational EM: The latent-variable likelihood sums over all configurations and is generally intractable, motivating a variational expectation-maximization procedure.The conditional distribution of latent groups does not factorize because observations couple individuals at each time point.
  • Variational EM: The variational family treats individuals independently while preserving an inhomogeneous Markov-chain distribution through time for each individual.Its marginal probabilities are obtained from initial probabilities and variational transition probabilities.
  • Parameter updates: VEM alternates optimization over variational distributions and model parameters, including transition, connectivity, initialization, stationary-distribution, and edge-distribution parameters.The connectivity updates support Bernoulli, finite-space, Poisson, and Gaussian edge models.
  • Model selection: The ICL criterion selects the number of groups while penalizing transition and connectivity parameters in a family-dependent manner.The connectivity penalty depends on the chosen edge-distribution family.
  • Algorithm initialization: Initialization uses k-means to produce node memberships constant across time, which works best when memberships vary little but can hurt performance as time points increase.The authors connect occasional performance decreases at larger T to the greater chance of group changes relative to this initialization.

4. Synthetic experiments

Synthetic experiments evaluate clustering and model-selection performance across group stabilities, connectivity separations, time horizons, and competing procedures. The method generally recovers smooth group trajectories in identifiable settings and selects the correct group count in most simulations.

  • Clustering performances: Global ARI measures smooth recovery across time, whereas averaged ARI measures time-local recovery; global ARI is generally lower.In the affiliation model, averaged ARI can remain close to 1 while global ARI is low.
  • Experimental design: Synthetic experiments use binary dynamic graphs with N = 100 nodes, T ∈ {5, 10} time points, and Q = 2 latent groups.The experiments vary transition stability and Bernoulli connectivity parameters, including an affiliation case.
  • Clustering performances: In identifiable cases, global ARI values exceed 0.8 when group stability is not too low or connectivity behaviors are sufficiently separated.Clustering performance increases with group stability and with better separation between group connectivity behaviors.
  • Clustering performances: Increasing T from 5 to 10 usually slightly increases ARI and reduces variance, but performance decreases for low or medium stability with β = low+.The authors attribute this exception to constant-in-time initialization becoming farther from memberships that change during longer sequences.
  • Parameter estimation: Transition-parameter MSE is below 2% in most cases, although it can reach 15% when groups are not globally recovered.The authors interpret the generally small errors as evidence that group-membership dynamics are captured.
  • Comparison with existing methods: The proposed procedure globally outperforms Yang et al.’s method in ARI, retaining good partitions in intermediate cases where Yang et al.’s performance drops.Yang et al.’s strongest results are associated with especially favorable initialization.
  • Model selection: 88% of simulations recover the correct number of groups with ICL.When ICL selects three groups, the four-group classification has ARI below 80%, suggesting the classification problem is not resolved by penalization alone.

5. Revealing social structure in dynamic contact networks

The dynamic SBM reveals stable communities, isolated students, and gender-linked interaction patterns in high-school and animal contact networks. Modeling interaction frequency alongside presence or absence exposes structure that a binary model misses.

  • Encounters among high school students: Face-to-face encounters were aggregated into four undirected weighted daily networks, with interaction frequencies discretized into three bins.The dataset retained 27 students present on every day.
  • Encounters among high school students: Group 1 captured seven stable, low-interacting students, highlighting dynamics of aloneness beyond evolving community structure.These students generally interacted with only a small number of partners.
  • Encounters among high school students: Most between-group moves were made by male students, while female students tended to remain in groups 1 and 4, providing evidence of gender homophily.Group 3 was exclusively male, whereas group 1 included a persistent female backbone.
  • Encounters among high school students: The binary model did not capture interesting structure, indicating that both interaction presence and frequency matter in this network.The authors therefore model frequency explicitly through the weighted-edge framework.
  • Social interactions between animals: For animal networks, the method identified sparrow communities across seasons and modeled onager interactions using an extended model for changing node presence.The sparrow data contained 3 seasonal networks with turnover, while the onager data contained 4 monthly networks.

A. Counter example of identifiability when groups memberships and connectivity parameters vary freely

When group memberships and connectivity parameters both vary freely over time, different parameter settings can generate the same observation distribution. This demonstrates non-identifiability beyond ordinary global label switching.

  • Counter example of identifiability when groups memberships and connectivity parameters vary freely: A two-group construction uses a fixed latent configuration under one parameter and alternating group switches under another.Both constructions share the stationary distribution (1/2, 1/2).
  • Counter example of identifiability when groups memberships and connectivity parameters vary freely: The second construction swaps within-group parameters across time while leaving the across-group parameter unchanged.This preserves the observation distribution despite changing the latent dynamics.
  • Counter example of identifiability when groups memberships and connectivity parameters vary freely: The two parameter values are not related by a single global permutation, yet they produce the same distribution on observations.Thus the model is not identifiable up to label switching when both memberships and connectivity vary without constraints.

B. Non identifiability in affiliation case (planted partition)

In the dynamic affiliation SBM, group labels can switch freely across time, making the transition matrix difficult or impossible to identify without additional constraints.

  • Identifying the full parameter set in a binary affiliation SBM is difficult, with existing results remaining partial.
  • Under natural assumptions, the dynamic affiliation model may identify (α, β, γ), but not its transition parameters without a constraint on π.
  • Even knowing the proportions of four mixture components does not make the individual transition probabilities π identifiable.
  • Empirical evidence of label switching in the affiliation setup is reported in the main manuscript.

C. Optimization with respect to τ(i, q)

The variational optimization over τ(i, q) is characterized by an exact fixed-point equation, alongside the approximation used in the main method.

  • The values τ̂(i, q) maximizing J(θ, τ) satisfy an exact fixed-point equation.
  • For t = 2, the equation uses the convention q_t−1 = q and is compared with the approximation in equation (7).

D. Estimation of γ and model selection: specific examples

The paper gives distribution-specific updates for γ and corresponding ICL expressions, but model-selection behavior depends strongly on the observation family.

  • The M-step update for γ depends on the chosen parametric family, with ICL expressions provided for several families.
  • Model selection: For the other setups, model selection is performed through the ICL criterion and its specified penalty term.
  • Bernoulli: For Bernoulli observations, θ reduces to (π, β), with β_t constrained to remain constant over time.
  • Finite space: For finite-valued observations, γ assigns probabilities to known nonzero values, and the updates also apply to disjoint bins.
  • Model selection: The finite-distribution setup receives no proposed criterion for selecting Q because competition with the number of bins M often selects Q = 2.
  • Poisson: For Poisson observations, mixing the truncated Poisson family with a Dirac mass at zero yields a zero-inflated or zero-deflated Poisson model.
  • Gaussian homoscedastic: For Gaussian observations, the paper uses a homoscedastic model with γ = (µ, σ²) and variance constant across groups.

E. Extension to varying number of nodes

The model can accommodate actors entering or leaving over time by treating absent nodes separately, excluding their missing observations from the likelihood.

  • The extension starts from a total individual set V and allows a time-specific present subset V^t with cardinality N_t.
  • Each time-specific adjacency matrix retains size N × N, while observations involving absent nodes are deterministically set to zero.
  • The latent state space is extended to Q_a = Q ∪ {a}, where a denotes absence and present nodes remain constrained to Q.
  • For each individual, latent states form an inhomogeneous Markov chain on Q_a, with transitions constrained according to presence.
  • The transition process on Q is stationary, but extending it with absence makes the complete latent chain nonstationary.
  • Absent nodes contribute to the likelihood only through the trajectory portions when they are present, and the variational algorithm generalizes readily.

F. Supplementary figures

The supplementary figures report estimation runtime, transition-matrix estimation error, clustering accuracy, likelihood-based group-number assessment, and subgroup analyses across simulated and empirical datasets.

  • Runtime: Elapsed-time boxplots evaluate the estimation algorithm, including initialization, across N = 500, 1000 and Q = 5, 10.The simulations use Bernoulli data with β = medium+ and high group stability over 50 datasets.
  • Estimation accuracy: MSE boxplots assess transition-matrix π estimation across πlow, πmedium, πhigh, five β setups, and T = 5 or 10 time points.The β setups are low−, low+, medium−, medium+, and affiliation case.
  • Clustering accuracy: Global and averaged ARI boxplots evaluate the combination of the proposed initialization strategy with Yang et al.’s algorithm across the same π, β, and T configurations.White boxplots represent global ARI and grey boxplots represent averaged ARI.
  • Model selection: Complete-data log-likelihood is plotted for different numbers of groups on the interaction dataset from the PC class.The dataset is from Fournet and Barrat (2014).
  • Subgroup analysis: A supplementary figure reproduces the main-manuscript analysis separately for 12 female and 15 male students.The female-student results are shown on the left and the male-student results on the right.
Loading 1506.07464v2…