Change point detection in network models: preferential attachment and long range dependence
From MaRDI portal
Publication:1751962
Abstract: Inspired by empirical data on real world complex networks, the last few years have seen an explosion in proposed generative models to understand and explain observed properties of real world networks, including power law degree distribution and "small world" distance scaling. In this context, a natural question is the phenomenon of {it change point}, understanding how abrupt changes in parameters driving the network model change structural properties of the network. We study this phenomenon in one popular class of dynamically evolving networks: preferential attachment models. We derive asymptotic properties of various functionals of the network including the degree distribution as well as maximal degree asymptotics, in essence showing that the change point does effect the degree distribution but does {�f not} change the degree exponent. This provides further evidence for long range dependence and sensitive dependence of the evolution of the process on the initial evolution of the process in such self-reinforced systems. We then propose an estimator for the change point and prove consistency properties of this estimator. The methodology developed highlights the effect of the non-ergodic nature of the evolution of the network on classical change point estimators.
Recommendations
- Fitting the linear preferential attachment model
- Changepoint Inference for Erdős–Rényi Random Graphs
- On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees
- Inference for the degree distributions of preferential attachment networks with zero-degree nodes
- Consistent estimation in general sublinear preferential attachment trees
Cites work
- A general model of web graphs
- Asymptotic normality of degree counts in a preferential attachment model
- Bayesian anomaly detection methods for social networks
- Changepoint Inference for Erdős–Rényi Random Graphs
- Complex graphs and networks
- Degree distribution nearby the origin of a preferential attachment graph
- Detection of abrupt changes: theory and application
- Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems
- Emergence of Scaling in Random Networks
- Finding Adam in random growing trees
- Functional limit theorems for dependent variables
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 3951715 (Why is no real title available?)
- scientific article; zbMATH DE number 4053643 (Why is no real title available?)
- scientific article; zbMATH DE number 44889 (Why is no real title available?)
- scientific article; zbMATH DE number 3555176 (Why is no real title available?)
- scientific article; zbMATH DE number 1048663 (Why is no real title available?)
- scientific article; zbMATH DE number 1487502 (Why is no real title available?)
- scientific article; zbMATH DE number 1487661 (Why is no real title available?)
- scientific article; zbMATH DE number 1866312 (Why is no real title available?)
- Limit theorems for sums determined by branching and other exponentially growing processes
- Markov Chains
- Minimax Methods for Multihypothesis Sequential Testing and Change-Point Detection Problems
- Networks. An introduction.
- Nonparametric change-point estimation
- ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS
- On Optimum Methods in Quickest Detection Problems
- Partial Sums of Infinite Series, and How They Grow
- Random graph dynamics
- Random graphs and complex networks. Volume 1
- Random trees and general branching processes
- Robustness and Vulnerability of Scale-Free Random Graphs
- Scaling limits and influence of the seed graph in preferential attachment trees
- Scan statistics on Enron graphs
- Sequential analysis. Tests and confidence intervals
- Spectra of large random trees
- Statistical mechanics of complex networks
- The degree sequence of a scale-free random graph process
- The growth and composition of branching populations
- The Structure and Function of Complex Networks
- Twitter event networks and the superstar model
Cited in
(12)- Sequential network change detection with its applications to ad impact relation analysis
- The Bethe Hessian and information theoretic approaches for online change-point detection in network data
- Correlated randomly growing graphs
- Detection and localization of change-points in high-dimensional network traffic data
- Lyapunov-based anomaly detection in preferential attachment networks
- Changepoint Inference for Erdős–Rényi Random Graphs
- Detecting structured signals in Ising models
- Time‐varying β‐model for dynamic directed networks
- Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point
- A new model for preferential attachment scheme with time-varying parameters
- On the impossibility of detecting a late change-point in the preferential attachment random graph model
- Detecting a late changepoint in the preferential attachment model
This page was built for publication: Change point detection in network models: preferential attachment and long range dependence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751962)
