Likelihood-based anomaly detection in preferential attachment networks

2026/07/01 by Qiu Liang, Remco van der Hofstad, Nelly Litvak
Computer Science · Mathematics · #cs.SI #math.PR

paper · pdf

arxiv created 2026/07/01 · arxiv updated 2026/08/07

Abstract

Preferential attachment (PA) network is a widely used model for capturing the growth dynamics of real-world networks, in which newly arriving vertices are more likely to connect to existing vertices with higher degrees. In this paper, we consider a setting in which an anomalous vertex appears at some time point and receives edges with an additional attachment advantage governed by a parameter β, while ordinary vertices continue to follow the PA mechanism with parameter δ. Detecting such anomalies is challenging due to the high variability in degree growth in PA networks and the limited information available when the anomaly arrives late in the network evolution. We propose an iterative parameter estimation procedure together with a likelihood-based detection framework. Simulation results show that the proposed procedure provides accurate estimation of the parameters β and δ. Detection performance depends on the time of anomaly occurrence: anomalies arising at midway stages of the network evolution are detected most reliably, whereas very early and late anomalies remain challenging, particularly when the parameter β is small.

Citations

• Degrees in Preferential Attachment Networks with an Anomaly
• A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
• 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
• Likelihood-based Inference for Random Networks with Changepoints
• Anomaly Detection in Dynamic Graphs via Transformer
• Laplacian Change Point Detection for Dynamic Graphs
• Fluctuation Bounds for Continuous Time Branching Processes and Evolution of Growing Trees With a Change Point
• The spread of true and false news online
• On the Asymptotic Normality of Estimating the Affine Preferential Attachment Network Models with Random Initial Degrees
• Anomaly detection in online social networks
• Graph-based Anomaly Detection and Description: A Survey
• Detecting change points in the large-scale structure of evolving networks
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Twitter event networks and the Superstar model
• Bayesian anomaly detection methods for social networks
• Evolution of the social network of scientific collaborations