Random graph models for dynamic networks

I. INTRODUCTION

• The paper focuses on successive network snapshots over a fixed node set, with edges appearing or disappearing over time.Snapshots are usually, though not always, evenly spaced.Source: §I · p. 1
• Because successive snapshots can be correlated, analyzing each snapshot independently can miss whether equally prevalent edges change at different rates.The paper’s Markov-process approach distinguishes links that are present in half the snapshots but flicker at different speeds.Source: §I · p. 1
• The models generate entire network histories, rather than treating a single network as the fundamental unit of analysis.Edge appearance and disappearance follow continuous-time Markov processes whose rates can differ across node pairs.Source: §I · p. 1
• The paper generalizes the random graph, configuration model, and degree-corrected stochastic block model to dynamic networks.The models target evolving edge probabilities, node degrees, and large-scale structure such as communities.Source: §I · p. 1
• Prior dynamic block models include approaches with changing community memberships and a Markov edge-dynamics model with elements in common with this paper.Other cited approaches include multilayer block models, whose layers are unordered and need not be more similar when adjacent.Source: §I · p. 2

II. DYNAMIC NETWORK MODELS

• The observed data are T snapshots at integer times, plus an initial state, while the network continues evolving unobserved between snapshots.Snapshots are assumed evenly spaced in this setup.Source: §II · p. 2
• Each edge follows a continuous-time Markov process with constant appearance and disappearance rates that can vary by node pair.Rates may depend on latent node properties, allowing the models to represent fluctuating density, degree distributions, or community structure.Source: §II · p. 2
• Per-snapshot transition probabilities can be used in place of the continuous-time rates and calculated from λ and µ when needed.The equations describe the probabilities of edge appearance and disappearance between snapshots.Source: §II · p. 2

A. The dynamic random graph

• At each snapshot, absent edges appear with probability α and present edges disappear with probability β.The resulting T + 1 snapshots are represented by symmetric adjacency matrices.Source: A. The dynamic random graph · p. 3
• In the long-time limit, every node pair has edge probability p = λ/(λ + µ) = α/(α + β), so the stationary distribution is G(n, p).This stationary distribution is the sense in which the model generalizes the static random graph.Source: A. The dynamic random graph · p. 3
• The maximum-likelihood estimates of α and β differ from naive transition fractions because the initial snapshot is drawn from a stationary distribution that depends on both rates.As T → ∞, the estimates converge to the naive values.Source: A. The dynamic random graph · p. 4
• Because the estimates depend on p, the paper solves the rate equations iteratively from a suitable initial condition.Closed-form equations are possible but more complicated.Source: A. The dynamic random graph · p. 4
• The fitted rates describe edge-change rates and adjacent-snapshot correlations, while α/(α + β) estimates average network density.The likelihood conditions each later snapshot on the preceding one under the Markov assumption.Source: A. The dynamic random graph · pp. 3–4
• The model is illustrative but too simple for many real networks, generating Poisson degree distributions unlike their typically broad, strongly non-Poisson distributions.The paper next turns to a dynamic configuration model to address this shortcoming.Source: A. The dynamic random graph · p. 4

B. Dynamic random graphs with arbitrary expected degrees

• At stationarity, edge counts between node pairs are Poisson with mean d_i d_j/2m, making the model equivalent to Chung–Lu.The model allows multiedges and self-loops, which have vanishing density as n grows when the degree distribution has finite mean and variance.Source: B. Dynamic random graphs with… · pp. 4–5
• The model adds edges between pair i, j at rate µd_i d_j/2m and removes each existing edge at rate µ.It initializes from the Chung–Lu model and generates snapshots from the ensuing continuous-time process.Source: B. Dynamic random graphs with… · p. 5
• The degree estimate divides a node’s observed edge count by 1 + Tβ, the effective number of independent observations per node pair.When β = 0 there is effectively one measurement; when β = 1, the T + 1 snapshots are independent.Source: B. Dynamic random graphs with… · p. 6
• Maximum-likelihood fitting estimates the rate parameter β and expected node degrees d_i using self-consistent equations.The resulting estimates generally differ from naive data averages because the initial state is drawn from a parameter-dependent stationary distribution; that advantage vanishes as T grows.Source: B. Dynamic random graphs with… · p. 6
• The dynamic model assigns each node a single expected-degree parameter d_i, a measure of its propensity to connect despite fluctuating actual degrees.The authors propose this as a principled degree-like quantity for dynamic networks.Source: B. Dynamic random graphs with… · pp. 6–7

C. Dynamic block models

• The degree-like parameters θ_i are identifiable only up to a group-specific multiplicative constant, so the model normalizes their sum to 1 within each group.This normalization removes the remaining degrees of freedom.Source: C. Dynamic block models · p. 7
• The model assigns groups and degree-like parameters to nodes, with edge appearance rates and removal rates depending on the groups of each node pair.The initial state is drawn from the static degree-corrected block model; its within- and between-group densities are controlled by ω_rs.Source: C. Dynamic block models · p. 7
• The model’s stationary state is equivalent to the degree-corrected stochastic block model.It permits community structure while accommodating chosen expected degrees for nodes.Source: C. Dynamic block models · p. 7
• Fitting estimates the group assignments and parameters β_rs, ω_rs, and θ_i by maximizing the likelihood.The parameters are solved self-consistently, while group assignments are optimized through the profile likelihood.Source: C. Dynamic block models · pp. 7–9
• The group-assignment search uses repeated single-node moves from a random starting assignment and retains the state with the highest profile likelihood.Because random initial conditions can yield different results, the authors recommend multiple runs and choosing the best overall profile likelihood.Source: C. Dynamic block models · p. 9
• Unlike the alternative dynamic block model described, this model assumes fixed group memberships and correlated edges between snapshots.The contrasted model assumes time-varying group memberships and independent edges between snapshots.Source: C. Dynamic block models · p. 9

III. APPLICATIONS

• The applications fit observed dynamic network data to the dynamic configuration model and the dynamic block model.The passage identifies the models used but gives no application results.Source: §III · p. 9

A. Synthetic networks

• The tests use n = 500 nodes in two equal groups, with an initial state and up to five further snapshots, and quantify recovery using normalized mutual information.The networks are generated from the same dynamic block model used for fitting; δ interpolates community structure, while η controls dynamic heterogeneity without changing expected degree or average density.Source: A. Synthetic networks · pp. 9–10
• With η = 1, edge dynamics let the algorithm recover communities below the static detectability threshold, but only when T is large.Within-group edges are more persistent than between-group edges, providing a signal beyond time-averaged edge probabilities.Source: A. Synthetic networks · p. 10
• As community strength δ weakens, recovery declines; using more snapshots partly offsets this and can surpass the static detectability threshold.Panel (a) uses η = 0 and βuniform = 0.4; each plotted data point averages 30 networks with n = 500 and average degree c = 16.Source: A. Synthetic networks · p. 10, Figure 1 · p. 10
• With δ = 0, increasing η and T improves recovery from dynamics alone, suggesting a detectability threshold whose location tends to zero as T → ∞.Here βuniform = 0.4, βin = 0, and βout = 0.8.Source: A. Synthetic networks · p. 10

• Across three real-world technological and social network examples, the dynamic models and algorithms perform better than static methods.Source: B. Real-world examples · p. 11

Internet graph

• For the Internet, β=0.0896 implies over 90% of edges remain intact between snapshots, while observed densification and degree-dependent edge removal depart from model assumptions.Source: B. Real-world examples · pp. 11–12
• Treating correlated snapshots as independent underestimates uncertainty in degree estimates, and maximum-likelihood degree estimates can decrease when no new edges appear.Source: B. Real-world examples · p. 11

Friendship network

• For friendship groups, the dynamic model correctly assigns 64% of students, versus 52% for the static aggregate model and 33% for random coloring.Source: B. Real-world examples · p. 12, Figure 3 · p. 12

Proximity network

• In the proximity network, classification error is 4.1% for the dynamic model and 5.7% for the static model.Source: B. Real-world examples · p. 13, Figure 4 · p. 13
• Proximity-network β estimates are 0.51 within classes, 0.75 across classes in the same specialty, and 0.94 across specialties; reported persistence is nearly 50% within classes versus about 6% across specialties.Source: B. Real-world examples · p. 13

IV. CONCLUSIONS

• The models and fitting algorithms estimate rates of change, node degrees, and community structure, and were tested on synthetic benchmarks and real-world dynamic-network data.The models generalize the Erdős–Rényi random graph, configuration model, and degree-corrected stochastic block model.Source: §IV · p. 13
• The work focuses exclusively on edge dynamics; extending it to changing nodes or node properties is identified as a natural direction.The authors also identify relaxing the continuous-time Markov assumption as a possible extension.Source: §IV · p. 13
• Community-detection calculations assume the number of communities is known, leaving methods for determining that number in dynamic networks as an open question.Source: §IV · p. 14