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

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. (2023)) that when observing only the unlabeled graph, detection of the change is not possible for Δ_n = n(n^1/2). In this work, we make a step towards proving the conjecture by proving the impossibility of detecting the change when Δ_n = n(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.