Damage detection via shortest-path network sampling

Ciulla, F., Perra, N., Baronchelli, A. & Vespignani, A. (2014). Damage detection via shortest-path network sampling. Physical Review E (PRE), 89(5), 052816. doi: 10.1103/PhysRevE.89.052816

[img]
Preview
PDF - Accepted Version
Download (7MB) | Preview

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.

Item Type: Article
Additional Information: Copyright American Physical Society 2014
Subjects: Q Science > QA Mathematics
Divisions: School of Engineering & Mathematical Sciences
Related URLs:
URI: http://openaccess.city.ac.uk/id/eprint/4779

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics