# Estimating Traffic and Anomaly Maps via Network Tomography

arXiv: https://arxiv.org/abs/1407.1660 · HTML: https://mlsanity.com/paper/1407.1660/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2014.

## Built on by (most cited first, 6 of 6)

- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Proximal Interacting Particle Langevin Algorithms](https://mlsanity.com/paper/2406.14292/) (2024)
- [Adaptive Anomaly Detection in Network Flows with Low-Rank Tensor Decompositions and Deep Unrolling](https://mlsanity.com/paper/2409.11529/) (2024)
- [PLATONT: Learning a Platonic Representation for Unified Network Tomography](https://mlsanity.com/paper/2511.15251/) (2025)
- [On the (Generative) Linear Sketching Problem](https://mlsanity.com/paper/2603.14474/) (2026)

## Abstract (arXiv)

Mapping origin-destination (OD) network traffic is pivotal for network management and proactive security tasks. However, lack of sufficient flow-level measurements as well as potential anomalies pose major challenges towards this goal. Leveraging the spatiotemporal correlation of nominal traffic, and the sparse nature of anomalies, this paper brings forth a novel framework to map out nominal and anomalous traffic, which treats jointly important network monitoring tasks including traffic estimation, anomaly detection, and traffic interpolation. To this end, a convex program is first formulated with nuclear and ℓ1-norm regularization to effect sparsity and low rank for the nominal and anomalous traffic with only the link counts and a it small subset of OD-flow counts. Analysis and simulations confirm that the proposed estimator can em exactly recover sufficiently low-dimensional nominal traffic and sporadic anomalies so long as the routing paths are sufficiently "spread-out" across the network, and an adequate amount of flow counts are randomly sampled. The results offer valuable insights about data acquisition strategies and network scenaria giving rise to accurate traffic estimation. For practical networks where the aforementioned conditions are possibly violated, the inherent spatiotemporal traffic patterns are taken into account by adopting a Bayesian approach along with a bilinear characterization of the nuclear and ℓ1 norms. The resultant nonconvex program involves quadratic regularizers with correlation matrices, learned systematically from (cyclo)stationary historical data. Alternating-minimization based algorithms with provable convergence are also developed to procure the estimates. Insightful tests with synthetic and real Internet data corroborate the effectiveness of the novel schemes.