On the impossibility of detecting a late change-point in the preferential attachment random graph model

2024/07/26 by Kaddouri, Ibrahim, Naulet, Zacharie, Gassiat, Élisabeth
#FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2407.18685

Abstract

We consider the problem of late change-point detection under the preferential attachment random graph model with time dependent attachment function. This can be formulated as a hypothesis testing problem where the null hypothesis corresponds to a preferential attachment model with a constant affine attachment parameter δ₀ and the alternative corresponds to a preferential attachment model where the affine attachment parameter changes from δ₀ to δ₁ at a time τ_n = n - Δ_n where 0≤ Δ_n ≤ n and n is the size of the graph. It was conjectured in Bet et al. that when observing only the unlabeled graph, detection of the change is not possible for Δ_n = o(n^1/2). In this work, we make a step towards proving the conjecture by proving the impossibility of detecting the change when Δ_n = o(n^1/3). We also study change-point detection in the case where the labeled graph is observed and show that change-point detection is possible if and only if Δ_n → ∞, thereby exhibiting a strong difference between the two settings.

Cited by

• Likelihood-based anomaly detection in preferential attachment networks

Related

• Detecting a late changepoint in the preferential attachment model
• A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
• A new model for preferential attachment scheme with time-varying parameters
• Change point detection in Network models: Preferential attachment and long range dependence
• Random walk attachment graphs