title: Damage detection via shortest-path network sampling.
abstract: Large networked systems are constantly exposed to local damages and failures that can alter their functionality. The knowledge of the structure of these systems is, however, often derived through sampling strategies whose effectiveness at damage detection has not been thoroughly investigated so far. Here, we study the performance of shortest-path sampling for damage detection in large-scale networks. We define appropriate metrics to characterize the sampling process before and after the damage, providing statistical estimates for the status of nodes (damaged, not damaged). The proposed methodology is flexible and allows tuning the trade-off between the accuracy of the damage detection and the number of probes used to sample the network. We test and measure the efficiency of our approach considering both synthetic and real networks data. Remarkably, in all of the systems studied, the number of correctly identified damaged nodes exceeds the number of false positives, allowing us to uncover the damage precisely.
authors.affiliation: Laboratory for the Modeling of Biological and Socio-technical Systems, Northeastern University, Boston, Massachusetts 02115, USA.
authors.forename: Fabio
authors.initials: F
authors.lastname: Ciulla
authors.affiliation: Laboratory for the Modeling of Biological and Socio-technical Systems, Northeastern University, Boston, Massachusetts 02115, USA.
authors.forename: Nicola
authors.initials: N
authors.lastname: Perra
authors.affiliation: Department of Mathematics, City University London, Northampton Square, London EC1V 0HB, United Kingdom.
authors.forename: Andrea
authors.initials: A
authors.lastname: Baronchelli
authors.affiliation: Laboratory for the Modeling of Biological and Socio-technical Systems, Northeastern University, Boston, Massachusetts 02115, USA and Institute for Scientific Interchange (ISI), Torino, Italy.
authors.forename: Alessandro
authors.initials: A
authors.lastname: Vespignani
mesh_terms: D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D020407:Internet / Q000706:statistics & numerical data*; D015233:Models, Statistical; D018401:Sample Size; D012815:Signal Processing, Computer-Assisted