Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.10925 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918140563161088 |
|---|---|
| author | Hajjouz, Abdulkader Avksentieva, Elena |
| author_facet | Hajjouz, Abdulkader Avksentieva, Elena |
| contents | 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^2 * chi^2(Bern(p+Delta) || Bern(p)), where chi^2 ~ Delta^2 / [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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10925 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Detectability Thresholds for Network Attacks on Static Graphs and Temporal Networks: Information-Theoretic Limits and Nearly-Optimal Tests Hajjouz, Abdulkader Avksentieva, Elena Information Theory 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^2 * chi^2(Bern(p+Delta) || Bern(p)), where chi^2 ~ Delta^2 / [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. |
| title | Detectability Thresholds for Network Attacks on Static Graphs and Temporal Networks: Information-Theoretic Limits and Nearly-Optimal Tests |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.10925 |