We develop a consolidated theory for the detectability of network-borne attacks under two canonical observation models: (i) a static graph drawn from an Erdos-Renyi background with a planted anomalous community, and (ii) a temporal interaction network modeled by multivariate point processes (Poisson or Hawkes). Our main contribution is to match, up to universal constants, information-theoretic lower and upper bounds that govern when reliable testing is possible. In the static case, the core quantity is the accumulated edgewise signal k² * chi² (Bern (p+Delta) || Bern (p) ), where chi² ~ Delta² / p (1-p) for small Delta; detection is impossible when this falls below c * log n, and a non-backtracking spectral statistic succeeds above C * log n. In the temporal case, detectability is controlled by the KL information rate I contributed by internal edges over a window of length T, yielding a threshold T I >= log n; a likelihood-based cumulative-sum (CUSUM) test achieves first-order optimal delay approximately abs (log alpha) / I at false-alarm level alpha. We also quantify robustness to bounded edge perturbations and outline conditional statistical-computational separations. A brief case study shows how to turn these bounds into concrete design choices.
Hajjouz et al. (Sat,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: