



























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 $δ_0$ and the alternative corresponds to a preferential attachment model where the affine attachment parameter changes from $δ_0$ to $δ_1$ at a time $τ_n = n - Δ_n$ where $0\leq Δ_n \leq 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 \to \infty$, thereby exhibiting a strong difference between the two settings.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。