Source-linked AI summary
Detecting change points in the large-scale structure of evolving networks
Leto Peel, Aaron Clauset
TL;DR
The paper addresses how to detect and characterize fundamental changes in the large-scale structure of evolving networks. It uses online graph-generative modeling with Bayesian model comparison, and reports accurate detection on synthetic data plus alignment with external shocks in two social networks.
Problem
Evolving networks require methods that identify when their large-scale structural norm changes and quantify the magnitude and type of change.
Method
The method learns graph distributions online with a generalized hierarchical random graph and compares change versus no-change models using a Bayesian hypothesis test.
Results
The method accurately determines whether, when, and how network structure changes, outperforming network-measure alternatives and recovering more known external shocks in two evolving social networks.
Takeaways & Limitations
Change-point detection can decompose evolving networks into probabilistically stationary structural periods for separate analysis and hypotheses about underlying processes.
Abstract
from arXiv · showhide
Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external "shocks" to these networks.
I. INTRODUCTION
The paper frames evolving-network change-point detection as identifying and characterizing shifts in large-scale interaction structure, rather than treating snapshots as stationary. It introduces an online probabilistic approach that compares change and no-change network models, then evaluates accuracy on synthetic and real social networks.
- Dynamic interactions can alter a network’s large-scale structure over time, so analyses must identify if, when, and how its structural norm changes.
- The approach selects a parametric network model and sliding window, infers change and no-change models, and uses a statistical hypothesis test to choose between them.
- Unlike approaches that reduce network sequences to scalar time series, this method models probability distributions over graphs using generative network models.
- The generalized hierarchical random graph models nested community structure at multiple scales and produces interpretable structural parameters for quantifying changes.
- Synthetic and real-network analyses show that the method determines whether, when, and how network structure changes and more accurately recovers timings of known external events than comparable techniques.
II. DEFINING A PROBABILITY DISTRIBUTION OVER NETWORKS
The GHRG defines a probabilistic distribution over networks by representing nested group structure with a dendrogram and connection probabilities. Its flexible hierarchy captures structures ranging from random graphs to fully hierarchical organizations while supporting interpretable structural changes.
- The model generalizes HRG by allowing assortative and disassortative communities, multiscale structure, and non-binary dendrograms.The non-binary relaxation addresses HRG non-identifiability and improves interpretability when quantifying structural variation.
- A Bayesian connection-probability model quantifies uncertainty about the network’s underlying generative structure.This avoids the limited uncertainty representation produced by setting probabilities directly to maximum-likelihood edge fractions.
- The GHRG represents nested vertex groups with a dendrogram, assigning each pair’s connection probability at their lowest common ancestor.The dendrogram leaves are network vertices, and each parameter governs connections between descendants of a tree node.
- Given a tree and connection probabilities, the GHRG defines a network distribution and likelihood based on edge counts within shared-ancestor groups.E_r counts observed edges and N_r counts possible edges for vertices whose common ancestor is r.
- The GHRG spans structures from an Erdős-Rényi random graph with one root node to the fully hierarchical classic HRG.Adding tree nodes increases the number of hierarchy levels and the variety of large-scale patterns represented.
III. LEARNING THE MODEL
The model is learned by Bayesian posterior inference over tree structures and parameters. MCMC samples bipartitions, a majority consensus forms a non-binary tree, and posterior updates incorporate observed edge counts.
- Fitting the GHRG requires searching over trees on N leaves and their link-probability sets using Bayesian inference and phylogenetic reconstruction techniques.Tree structures cannot be handled by classic convex optimization, so the search is performed explicitly.
- MCMC samples posterior bipartitions, whose majority consensus defines the estimated non-binary dendrogram.The consensus tree retains leaf divisions appearing in a majority of sampled binary trees.
- Posterior hyperparameters combine prior pseudocounts with empirically observed counts of present and absent edges.The resulting Bayesian update regularizes estimates and makes posterior uncertainty decrease as observations accumulate.
IV. DETECTING CHANGE POINTS IN NETWORKS
Change points are detected online by comparing change and no-change GHRG models over a fixed sliding window. A posterior Bayes factor triggers detection when it exceeds a threshold set by the desired false-positive rate.
- The method uses a posterior Bayes factor over a sliding window to test whether current normal-connectivity parameters have changed.The test compares a GHRG fitted with a change against one without a change.
A. Posterior Bayes factor
The posterior Bayes factor compares no-change and change hypotheses within a sliding window, integrating uncertainty through posterior marginal likelihoods. The method estimates the change location by maximizing the test statistic and detects it when the statistic crosses a stopping threshold.
- Structural interpretation: The GHRG’s hierarchy represents large-scale structure through parameters closer to the dendrogram root.The hierarchy spectrum ranges from a simple random graph to a complete hierarchical organization.
- Bayes factor: The posterior Bayes factor is a likelihood ratio between no-change and change models, using posterior marginal likelihoods rather than maximum-likelihood parameters.For the GHRG, posterior hyperparameters update the prior hyperparameters in the integrated likelihood.
- Hypotheses: The no-change hypothesis assigns one parameter set to all networks in the window, whereas the change hypothesis uses separate parameters before and after t_c.The change point is assumed to occur between consecutive snapshots.
- Timing and stopping: The estimated change time is the point between consecutive networks that maximizes the test statistic within the window.Detection occurs at the first current time τ for which the maximum statistic exceeds threshold h.
B. Parametric bootstrapping
The method calibrates change detection with a parametric bootstrap under the no-change GHRG model, selecting a threshold to control false positives.
- The threshold h controls the false-positive rate through the null distribution of the likelihood-ratio statistic gτ.The null distribution may deviate from χ2, motivating numerical estimation.
- The method samples networks from a fitted no-change GHRG model and calculates gτ to estimate its null distribution.The sampled distribution supports threshold selection and p-value calculation.
- A detection threshold is chosen so that p(gτ > h) equals the desired false-positive rate pfp.The test p-value is the proportion of null likelihood ratios exceeding the observed statistic.
- A change is declared when the p-value falls below the chosen threshold, with false detections bounded by pfp under the correct no-change model.
V. DETECTABILITY OF CHANGE POINTS
Synthetic experiments test detection across four change types and varying magnitudes, showing that the GHRG method is broadly effective while small changes remain difficult.
- Experimental design: The experiments use N = 30 sparse networks and test splitting, merging, fragmentation, and formation changes.Small networks make detection harder because limited data hinder estimation of structural norms.
- Experimental design: The structural index µ parameterizes transitions between the four change types, including merge µ̸ = 0.5 →µ = 0.5 and split µ = 0.5 →µ̸ = 0.5.
- Detection timing: Estimated change points are usually correct or slightly early, while merge and fragment changes are detected quickly.Detection time td measures how many post-change networks are needed before detection.
- Detection accuracy: False negatives remain high for simple network-measure methods, whereas the proposed method performs well across change types except for very small ∆µ.All methods have false-positive rates near the desired 0.05 level.
- Detection accuracy: For small split and merge changes, detectability can shift rapidly near a threshold when both network states approach Erdős-Rényi structure.The authors relate this pattern to the community-detection detectability phase transition.
VI. CHANGE POINTS IN REAL NETWORKS
The method is evaluated on two high-resolution social networks against known external events, using precision and recall as functions of detection delay.
- The empirical evaluation uses the MIT Reality Mining proximity network and the Enron email network, each representing a different interaction type.
- Performance is measured by precision and recall as functions of delay s between estimated change points and scheduled events.Precision concerns estimated points near known events; recall concerns known events near estimated points.
- Precision is the proportion of estimated change points occurring within delay s of known events, while recall is the proportion of known events matched by an estimated point.
A. Social proximity network
In the MIT proximity network, the GHRG method recovers nearly all known external events and reveals additional structural changes linked to social dynamics.
- The MIT dataset contains weekly proximity networks for 97 people over 35 weeks and 16 known external events.Edges represent physical proximity recorded during each week.
- Using w = 4, the GHRG method achieves lower recall than some baselines only in precision, but substantially outperforms them in recall.Clustering coefficient and mean degree slightly exceed GHRG precision.
- Simple network-measure methods detect few events, miss most known events, and show little consistency across methods.Mean degree and clustering coefficient each detect only 2 change points in total.
- The GHRG method identifies nearly all known events and additional points around Sponsor week, consistent with that event’s dramatic schedule shifts.
- The method finds more change points in Fall than Spring and provides interpretable structural changes consistent with new students establishing social patterns.By Spring, social patterns had largely stabilized and the Sponsor week perturbation was absent.
B. Enron email network
The GHRG method outperformed simple methods on the Enron email network, identifying change points that aligned with external events and a major structural shift around Enron online’s launch.
- The Enron network contains emails among 151 users observed in weekly snapshots from May 1999 to June 2002.The study identified 25 events across the three-year timeline and compared GHRG with simple methods.
- Results were highly consistent across window sizes w = {4, 8, 16}, although larger windows produced additional change points.The authors interpret window size as a temporal-resolution parameter, with longer windows giving more resolution.
- The GHRG method performed much better than the simple methods in both precision and recall.
- GHRG change points correlated well with key meetings, external events, and share price fluctuations.
- A particularly large structural change occurred around the launch of Enron online in November 1999.
VII. DISCUSSION
The method detects statistically significant changes in evolving networks by modeling shifts in probability distributions over graphs. It performed well on social-network data, but detectability depends on change magnitude and type, while inference remains computationally burdensome.
- Change points occur when the shape of an estimated probability distribution over networks changes significantly.
- Only changes of sufficiently large magnitude could be detected reliably in synthetic data.
- Merging and fragmentation changes were harder to detect accurately than splitting and formation changes.
- Mean degree, clustering coefficient, and mean geodesic path length methods had high false negative rates even for large structural changes.
- The method recovered the timing of many more known external shock events than network-measure methods in two high-resolution social networks.
- The current implementation’s computational burden lies in the MCMC procedure used to infer hierarchical structure.