Detecting Change Points in the Large-Scale Structure of Evolving Networks

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.

• Publication year

  2014

• Venue

  AAAI Conference on Artificial Intelligence

• Publication date

  2014-03-04

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1609/aaai.v29i1.9574arXiv 1403.0989
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning Latent Block Structure in Weighted Networks

  2014cited by this paper
• Network Hypothesis Testing Using Mixed Kronecker Product Graph Models

  2013cited by this paper
• Bayesian Hierarchical Community Discovery

  2013cited by this paper
• Evolving networks: Eras and turning points

  2013cited by this paper
• Adapting the Stochastic Block Model to Edge-Weighted Networks

  2013cited by this paper
• Persistence and periodicity in a dynamic proximity network

  2012cited by this paper
• Model selection for degree-corrected block models

  2012cited by this paper
• Topological feature based classification

  2011cited by this paper
• Phase transition in the detection of modules in sparse networks

  2011cited by this paper
• EVENT DETECTION IN TIME SERIES OF MOBILE COMMUNICATION GRAPHS

  2010cited by this paper
• Subgraph Detection Using Eigenvector L1 Norms

  2010cited by this paper
• On community outliers and their efficient detection in information networks

  2010cited by this paper
• Detection and localization of change-points in high-dimensional network traffic data

  2009cited by this paper
• Performance of modularity maximization in practical contexts.

  2009cited by this paper
• Network anomaly detection based on Eigen equation compression

  2009cited by this paper
• Discovering Structural Anomalies in Graph-Based Data

  2007cited by this paper
• An Introduction to the Bootstrap

  2007cited by this paper
• GraphScope: parameter-free mining of large time-evolving graphs

  2007cited by this paper
• Structural Inference of Hierarchies in Networks

  2006influential reference
• A Link Prediction Approach to Anomalous Email Detection

  2006cited by this paper
• Reality mining: sensing complex social systems

  2006cited by this paper
• Scan Statistics on Enron Graphs

  2005cited by this paper
• Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication

  2005cited by this paper
• Machine perception and learning of complex social systems

  2005cited by this paper
• Introducing the Enron Corpus

  2004cited by this paper
• Graph-based anomaly detection

  2003cited by this paper
• A classification of consensus methods for phylogenetics

  2001cited by this paper
• Estimation and Prediction for Stochastic Blockstructures

  2001cited by this paper
• Control Chart Tests Based on Geometric Moving Averages

  2000cited by this paper
• The calibration of P-values, posterior Bayes factors and the AIC from the posterior distribution of the likelihood

  1997cited by this paper
• Learning to change

  1995cited by this paper
• Detection of abrupt changes: theory and application

  1993cited by this paper
• Posterior Bayes Factors

  1991cited by this paper
• Cumulative Sum Charts

  1985cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper

• Embedding Birth-Death Processes within a Dynamic Stochastic Block Model

  2026cites this paper
• Structural Change Point Detection in Temporal Networks via MDL-Guided Tensor Decomposition

  2026cites this paper
• Multi-scale graph contrastive learning for community detection in dynamic graphs

  2026cites this paper
• A statistical test for network similarity

  2025cites this paper
• Forest Expression of Networks and their Applications

  2025cites this paper
• Early Detection and Attribution of Structural Changes in Dynamic Networks

  2025cites this paper
• User migration in blockchain-based online social networks through the lens of temporal node representation shift

  2025cites this paper
• Detecting and explaining structural changes in an evolving graph using a martingale

  2025cites this paper
• Multi-Rank Subspace Change-Point Detection for Monitoring Robotic Swarms

  2025cites this paper
• Modeling and Monitoring Dynamic, Directional, Sparse, Attributed Networks via a Dynamic Hurdle Regression Model with Latent Variables

  2025cites this paper
• Abnormal Evolution Pattern Recognition of Spatial Communities Based on Random Walk With Restart

  2025cites this paper
• Anomaly detection for live streaming graphs using copula based student-t process regression

  2025cites this paper
• HLSAD: Hodge Laplacian-based Simplicial Anomaly Detection

  2025influential citation
• Nonparametric online monitoring of dynamic networks

  2024cites this paper
• Multivariate Time Series Change-Point Detection with a Novel Pearson-like Scaled Bregman Divergence

  2024cites this paper
• VGGM: Variational Graph Gaussian Mixture Model for Unsupervised Change Point Detection in Dynamic Networks

  2024influential citation
• Random walk based snapshot clustering for detecting community dynamics in temporal networks

  2024cites this paper
• Dynamic Link and Flow Prediction in Bank Transfer Networks

  2024cites this paper
• Anomaly Detection in Graph Structured Data: A Survey

  2024cites this paper
• Quantifying community evolution in temporal networks

  2024cites this paper
• Structural Break Detection in Non-Stationary Network Vector Autoregression Models

  2024cites this paper
• Incremental Learning with Concept Drift Detection and Prototype-based Embeddings for Graph Stream Classification

  2024cites this paper
• Change Point Detection in Dynamic Graphs with Decoder-only Latent Space Model

  2024cites this paper
• Reproduction of scan B-statistic for kernel change-point detection algorithm

  2024cites this paper
• Graph Contrastive Learning for Tracking Dynamic Communities in Temporal Networks

  2024cites this paper
• Change Point Detection in Evolving Graph using Martingale

  2024cites this paper
• Describing group evolution in temporal data using multi-faceted events

  2024cites this paper
• Multi-view change point detection in dynamic networks

  2023cites this paper
• Anonymous Edge Representation for Inductive Anomaly Detection in Dynamic Bipartite Graphs

  2023cites this paper
• Network Change Detection Based on Random Walk in Latent Space

  2023cites this paper
• Equivalence relations and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e593" altimg="si1.svg"><mml:msup><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mi>p</mml:mi></mml:mrow></mml:msup></mml:math> distances between time series with application to the Black

  2023cites this paper
• Fast and Attributed Change Detection on Dynamic Graphs with Density of States

  2023cites this paper
• Online directed-structural change-point detection: A segment-wise time-varying dynamic Bayesian network approach

  2023cites this paper
• Detecting early-warning signals for social emergencies by temporal network sociomarkers

  2023cites this paper
• Modelling and monitoring social network change based on exponential random graph models

  2023cites this paper
• Assessing individual risk and the latent transmission of COVID-19 in a population with an interaction-driven temporal model

  2023cites this paper
• Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs

  2023cites this paper
• Modeling and monitoring multilayer attributed weighted directed networks via a generative model

  2023cites this paper
• Balancing Summarization and Change Detection in Graph Streams

  2023cites this paper
• CADENCE: Community-Aware Detection of Dynamic Network States

  2023cites this paper
• MoNetExplorer: A Visual Analytics System for Analyzing Dynamic Networks With Temporal Network Motifs

  2023cites this paper
• Temporal networks with node-specific memory: Unbiased inference of transition probabilities, relaxation times, and structural breaks

  2023cites this paper
• Community evolution prediction based on a self-adaptive timeframe in social networks

  2023cites this paper
• Training Neural Networks for Sequential Change-Point Detection

  2023cites this paper
• Attention-based hierarchical random graph model for structural inference of real-world networks

  2023cites this paper
• Generative Evolutionary Anomaly Detection in Dynamic Networks

  2023cites this paper
• Change Point Detection in Dynamic Networks via Regularized Tensor Decomposition

  2023influential citation
• Few-shot time-series anomaly detection with unsupervised domain adaptation

  2023cites this paper
• A unified approach of detecting phase transition in time-varying complex networks

  2023cites this paper
• Asymptotic Distribution-Free Change-Point Detection for Modern Data Based on a New Ranking Scheme

  2022cites this paper
• Latent Evolution Model for Change Point Detection in Time-varying Networks

  2022cites this paper
• Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction

  2022cites this paper
• Compressing network populations with modal networks reveal structural diversity

  2022cites this paper
• Sequential change‐point detection: Computation versus statistical performance

  2022cites this paper
• Graph similarity learning for change-point detection in dynamic networks

  2022cites this paper
• RING-CPD: Asymptotic Distribution-free Change-point Detection for Multivariate and Non-Euclidean Data

  2022cites this paper
• HB-DSBM: Modeling the Dynamic Complex Networks From Community Level to Node Level

  2022cites this paper
• Predicting stimulation index of information transmissions by local structural features in social networks

  2022cites this paper
• CP-Squared: A method for change point detection in core-periphery networks

  2022cites this paper
• Multiple Hypothesis Testing To Estimate The Number of Communities in Sparse Stochastic Block Models

  2022cites this paper
• Online Change Point Detection for Weighted and Directed Random Dot Product Graphs

  2022cites this paper
• Neural network-based CUSUM for online change-point detection

  2022cites this paper
• Clustering of heterogeneous populations of networks

  2021cites this paper
• Change-Point Detection in Dynamic Networks with Missing Links

  2021cites this paper
• TRIGGER: TempoRal Interaction Graph GenEratoR

  2021cites this paper
• On Topology Inference for Networked Dynamical Systems: Principles and Performances

  2021cites this paper
• Tailored Network Splitting for Community Evolution Prediction in Dynamic Social Networks

  2021cites this paper
• Scalable Change Point Detection for Dynamic Graphs

  2021cites this paper
• Optimality of Graph Scanning Statistic for Online Community Detection

  2021cites this paper
• Likelihood-based approach to discriminate mixtures of network models that vary in time

  2021cites this paper
• Tie-Decay Networks in Continuous Time and Eigenvector-Based Centralities

  2021cites this paper
• Sequential (Quickest) Change Detection: Classical Results and New Directions

  2021cites this paper
• Joint Learning of Feature Extraction and Clustering for Large-Scale Temporal Networks

  2021cites this paper
• The Bethe Hessian and Information Theoretic Approaches for Online Change-Point Detection in Network Data

  2021cites this paper
• Graph-based multiple change-point detection

  2021cites this paper
• Centrality informed embedding of networks for temporal feature extraction

  2021influential citation
• Botnet Detection Using Graph Based Feature Clustering

  2021cites this paper
• Succinct Representation of Dynamic Networks

  2021cites this paper
• Topology Inference for Network Systems: Causality Perspective and Nonasymptotic Performance

  2021cites this paper
• A Map of Approaches to Temporal Networks

  2021cites this paper
• Online Change Point Detection for Random Dot Product Graphs

  2021cites this paper
• Mining Fraudsters and Fraudulent Strategies in Large-Scale Mobile Social Networks

  2021cites this paper
• Robust Dynamic Clustering for Temporal Networks

  2021cites this paper
• Anomaly Detection in Edge Streams Using Term Frequency-Inverse Graph Frequency (TF-IGF) Concept

  2021cites this paper
• Social physics

  2021cites this paper
• SHM deformation monitoring for high-speed rail track slabs and Bayesian change point detection for the measurements

  2021cites this paper
• Event Detection on Dynamic Graphs

  2021cites this paper
• Change Detection in Core-Periphery Networks: A Case Study on Detecting Financial Crises in the Interbank Market

  2020cites this paper
• Adaptive Anomaly Detection for Dynamic Clinical Event Sequences

  2020cites this paper
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models

  2020cites this paper
• Mood Versus Identity: Studying the Influence of Affective States on Mobile Biometrics

  2020cites this paper
• Exponential random graph modeling for diagnosis of out‐of‐control signals in social network surveillance: Signal interpretation in social networks with ERG modeling

  2020cites this paper
• Differential Privacy for Evolving Network Based on GHRG

  2020cites this paper
• These Unprecedented Times: The Dynamic Pattern Of COVID-19 Deaths Around The World

  2020cites this paper
• Structure Prediction in Uncertain Temporal Networks

  2020cites this paper
• F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams

  2020cites this paper
• Change Point Detection in Dynamic Networks Based on Community Identification

  2020cites this paper
• Online Structural Change-Point Detection of High-dimensional Streaming Data via Dynamic Sparse Subspace Learning

  2020cites this paper
• Changepoint detection for data intensive settings

  2020cites this paper
• Multiple network embedding for anomaly detection in time series of graphs

  2020cites this paper