Damage detection via shortest path network sampling

F. Ciulla, N. Perra, A. Baronchelli, A. Vespignani
Physical Review E
89, 052816, (2014)
May 30, 2014


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.

Related publications