Dynamic stochastic blockmodels for time-evolving social networks

Kevin S. Xu; Alfred O. Hero

Source-linked AI summary

Dynamic stochastic blockmodels for time-evolving social networks

Kevin S. Xu, Alfred O. Hero

arXiv:1403.0921v1Mar 4, 2014cs.SIcs.LGphysics.soc-phstat.ME

TL;DR

Static network models provide limited representations of time-varying phenomena. This paper extends the stochastic blockmodel into a state-space dynamic network model and fits it online with an EKF augmented by local search. The EKF-based procedure is substantially faster than MCMC-based inference while achieving comparable accuracy, and it reveals temporal patterns in the Enron email network that aggregate email counts miss.

Problem
Most network models focus on static snapshots or temporal aggregates, despite complex phenomena such as social behavior changing over time.
Method
The paper models dynamic networks with latent evolving states and fits the resulting dynamic SBM online using an EKF augmented with local search.
Results
The EKF-based procedure is considerably faster than MCMC-based inference while showing comparable accuracy in recovering true states.
Takeaways & Limitations
Applying the procedure to Enron email data reveals class-to-class temporal dynamics that aggregate email counts do not identify.

Abstract

from arXiv · show

Significant efforts have gone into the development of statistical models for analyzing data in the form of networks, such as social networks. Most existing work has focused on modeling static networks, which represent either a single time snapshot or an aggregate view over time. There has been recent interest in statistical modeling of dynamic networks, which are observed at multiple points in time and offer a richer representation of many complex phenomena. In this paper, we present a state-space model for dynamic networks that extends the well-known stochastic blockmodel for static networks to the dynamic setting. We fit the model in a near-optimal manner using an extended Kalman filter (EKF) augmented with a local search. We demonstrate that the EKF-based algorithm performs competitively with a state-of-the-art algorithm based on Markov chain Monte Carlo sampling but is significantly less computationally demanding.

I. INTRODUCTION

The paper addresses the limits of static network models by representing evolving networks with latent time-varying states. It proposes an online state-space extension of the stochastic blockmodel, fitted with an EKF and local search.

Static network models capture snapshots or aggregates, but many complex phenomena, including social behavior, vary over time.
Dynamic networks are represented as sequences of graph snapshots in which nodes and edges may be added or removed.
The model combines an SBM for individual snapshots with a stochastic dynamic system for evolving unobserved states.
The online inference procedure uses a Gaussian approximation, an EKF, and local search to fit the model using past and present snapshots.
The paper extends earlier work with detailed approximation analysis and broader simulated and real-data performance evaluation.

B. Static stochastic blockmodels

The static stochastic blockmodel represents network edges through class-dependent probabilities and supports estimation with known or unknown class memberships. Block densities provide a sufficient statistic for estimating edge probabilities when memberships are known.

An SSBM uses a k × k matrix Θt, whose entries give edge probabilities between node classes.
Given class memberships, each adjacency-matrix entry is an independent Bernoulli realization governed by its corresponding block probability.
A priori blockmodeling estimates Θt with known or assumed memberships, whereas a posteriori blockmodeling estimates Θt and memberships jointly.
The a posteriori likelihood optimization over class memberships is combinatorial, motivating methods such as Gibbs sampling, label-switching, and spectral clustering.
The block-density matrix Y t is a sufficient statistic and maximum-likelihood estimate of Θt in the a priori setting.

C. Related work

The paper places its dynamic SBM among temporal network models and develops a state-space formulation with Gaussian observations, logistic parameters, and online EKF inference. The resulting procedure is designed to balance accuracy and computational cost.

Prior dynamic-network models include temporal ERGMs, latent-space and latent-factor models, random-dot-product processes, and temporal SBM extensions.
The proposed dynamic SBM extends the SSBM by treating block probabilities as states evolving through a linear dynamic system.
A Gaussian approximation models block densities as noisy observations of block probabilities, becoming more accurate as block sizes increase.
The logistic transformation maps unconstrained state entries in Ψt to probabilities in Θt for generating network observations.
The online EKF linearizes the nonlinear observation model around the predicted state to obtain a near-optimal estimate using observations through time t.
The a posteriori procedure computes block densities, applies EKF updates, and uses local search over class assignments.

B. A posteriori blockmodels

When class memberships are unknown, the method alternates EKF state estimation with posterior-based local search. It initializes memberships spectrally and seeks a MAP estimate of the class assignments.

A posteriori inference estimates class memberships jointly with Ψt by maximizing posterior state density over observations through time t.
The procedure alternates label-switching with EKF application to obtain a maximum a posteriori estimate of class memberships.
The posterior objective combines the current observation likelihood with the filtered temporal state density.
At the initial time step, spectral clustering on the first adjacency matrix produces the initial class-membership estimate ˆc0.
Local search is initialized from the previous time step because most applications are expected to have only a small fraction of nodes changing classes.

C. Time complexity

The EKF dominates per-step cost through matrix operations, while posterior estimation adds local-search evaluations over neighboring class assignments.

Computing block densities costs O(|E_t|), proportional to the number of observed edges at time t.
The EKF operates on k^2-dimensional observation and state vectors and is dominated by inverting a k^2 × k^2 matrix.
A posteriori blockmodeling adds a local search that visits |V_t|(k − 1) neighboring class assignments at each iteration.
Because matrix inversions are shared across class assignments, each local-search iteration has reduced complexity O(k^4).

D. Estimation of hyperparameters

The procedure specifies initial, observation-noise, and process-noise hyperparameters, using diffuse initialization, a plug-in observation covariance, and structured process covariance.

The four hyperparameters are the initial mean µ_0, initial covariance Γ_0, observation-noise covariance Σ_t, and process-noise covariance Γ_t.
Without prior edge-probability information, the initial state uses a diffuse prior whose variances approach ∞.
The observation-noise covariance Σ_t is estimated by substituting the current logistic-function estimate for Θ_t in the observation model.
The process-noise covariance Γ_t is assumed time-invariant but may be correlated, motivating a structured parameterization instead of estimating O(k^4) covariances individually.
The structure of Γ_t distinguishes diagonal variance sdiag from neighboring-cell covariance snb, reflecting the flattened matrix layout of ψ_t.

E. Approximation accuracy

The experiments support both approximations used by the EKF: Gaussian block-density observations and first-order linearization are accurate under the tested conditions.

The Gaussian approximation to binomial block densities is considered reasonable when n_t,ab θ_t,ab(1 − θ_t,ab) > 5.Because n_t,ab depends on class sizes, sufficiently large blocks can support the approximation even for small edge probabilities.
The EKF is only approximately optimal because its state estimate uses a first-order Taylor approximation about the predicted state.The paper argues this is sufficient when second-order bias and variance are negligible relative to observation noise.
The second-order EKF contribution is relatively small, suggesting that first-order Taylor linearization is sufficient.The comparison uses eigenvalues of the second-order term against observation-noise variances over simulation runs.
The EKF and both particle filters have comparable MSE, supporting the near-optimality of the EKF estimate.PF-G uses the Gaussian observation model, whereas PF-B uses the actual re-scaled binomial model.
The similar MSEs of PF-G and PF-B indicate little difference between the approximate Gaussian and actual observation distributions in this experiment.

A. Simulated stochastic blockmodels

The simulated networks use four evolving classes, and the EKF is compared with static SBM and PSA baselines under online and posterior settings.

The simulated network begins with 128 nodes divided into four classes of 32 nodes each.
At each time step, 10% of nodes leave their current class and are randomly assigned to one of the other three classes.
Each simulation run generates 10 time steps, with undirected graph snapshots drawn to match the referenced synthetic-network procedure.
The EKF is compared with a static SBM fit separately by spectral clustering and with PSA, which combines Gibbs sampling and simulated annealing.
Only the EKF and SSBM apply in the a priori setting, whereas EKF, SSBM, and PSA apply in the a posteriori setting.

1) Performance metrics:

Across simulated and real-network evaluations, EKF offers strong accuracy with lower computation time and greater hyperparameter robustness than competing methods, while scalability worsens as the number of classes grows.

Performance: The EKF achieves the lowest MSE in both a priori and a posteriori settings, whereas SSBM performs extremely poorly a posteriori because its true-class estimates are inaccurate.
Performance: Both EKF and PSA significantly outperform SSBM in class estimation accuracy; PSA is slightly more accurate, but requires about 6 minutes versus under 1 minute for EKF.
Hyperparameter sensitivity: The EKF is robust to hyperparameter choices, whereas PSA is extremely sensitive and can approach random class-assignment accuracy under some settings.
Hyperparameter sensitivity: Modularity-based hyperparameter selection is unsuitable when Θ_t is not diagonally dominant, and diffuse-prior choices can significantly reduce class-estimation accuracy.
Scalability: The EKF is about an order of magnitude faster than PSA at comparable accuracy, while SSBM is faster but has significantly poorer accuracy and lacks a temporal model.
Scalability: For k ≤8, EKF is an order of magnitude faster than PSA, but it becomes slower at k = 16 because its computational cost requires k^6 scaling.

B. MIT Reality Mining

The MIT Reality Mining experiment benchmarks dynamic class estimation using known participant affiliations and compares EKF, PSA, and static spectral clustering. Dynamic methods outperform the static baseline, while EKF achieves higher accuracy than PSA with lower computational cost.

Data and setup: 37 weekly proximity-network snapshots were constructed from Bluetooth scans of 94 MIT students and staff over one year.Periods with low participation near the experiment’s beginning and end were excluded.
Data and setup: Known participant affiliations provide ground-truth class memberships for evaluating dynamic network analysis methods.The affiliations correspond to communities identified in the time-aggregated physical-proximity network.
Class estimation: Both dynamic methods, EKF and PSA, estimate classes more accurately than SSBM spectral clustering.The comparison uses the summary in Table I.
Class estimation: EKF achieves higher class estimation accuracy than PSA despite PSA’s greater computational demands.The paper attributes this advantage to EKF’s temporal model for the edge-probability matrix Θt, which PSA does not use.
Dynamic link prediction: Dynamic SBM predictors combined with EWMA perform roughly comparably in AUC and all outperform EWMA alone.The a priori EKF adds hardly any computation time, while the a posteriori EKF is an order of magnitude faster than PSA.

2) Temporal dynamics:

The EKF tracks time-varying block edge probabilities in the Enron network and reveals class-specific temporal patterns around major events. These dynamics expose changes that aggregate email volume can miss and yield narrower uncertainty intervals than separate static fits.

Temporal dynamics: The EKF converts tracked logit states into estimated edge probabilities with confidence intervals for each time step.The states Ψt represent logits of the edge probabilities Θt; applying the logistic function produces ˆΘt|t.
Temporal dynamics: A large increase in CEO-originated edge probabilities occurs during week 89, when Jeffrey Skilling resigned.Inspection of the emails confirms the resignation as the cause of the increase.
Temporal dynamics: CEO-to-president edge probabilities increase as Enron’s financial situation worsens, while edges among other roles rise only after federal investigation begins.The selected probabilities are shown over time with 95% confidence intervals.
Temporal dynamics: CEO-to-president probabilities peak at three major events, whereas total weekly email volume peaks around only events 2 and 3.During Skilling’s resignation, overall volume stayed flat while CEO-originated email volume increased.
Temporal dynamics: Temporal modeling produces 95% confidence intervals that are 25% narrower on average than fitting a static SBM at each time step.Class-to-class probability dynamics, rather than whole-network probabilities, reveal the internal changes.