In this paper we study the node failure identification problem in undirected graphs by means of Boolean Network Tomography. We argue that vertex connectivity plays a central role. We show tight bounds on the maximal identifiability in a particular class of graphs, the Line of Sight networks. We prove slightly weaker bounds on arbitrary networks. Finally we initiate the study of maximal identifiability in random networks. We focus on two models: the classical Erdős-Rényi model, and that of Random Regular graphs. The framework proposed in the paper allows a probabilistic analysis of the identifiability in random networks giving a tradeoff between the number of monitors to place and the maximal identifiability.
Vertex-connectivity for node failure identification in boolean network tomography / Galesi, N.; Ranjbar, F.; Zito, M.. - 11931:(2019), pp. 79-95. (Intervento presentato al convegno 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2019 tenutosi a Munich; Germany) [10.1007/978-3-030-34405-4_5].
Vertex-connectivity for node failure identification in boolean network tomography
Galesi N.
Membro del Collaboration Group
;Ranjbar F.Membro del Collaboration Group
;
2019
Abstract
In this paper we study the node failure identification problem in undirected graphs by means of Boolean Network Tomography. We argue that vertex connectivity plays a central role. We show tight bounds on the maximal identifiability in a particular class of graphs, the Line of Sight networks. We prove slightly weaker bounds on arbitrary networks. Finally we initiate the study of maximal identifiability in random networks. We focus on two models: the classical Erdős-Rényi model, and that of Random Regular graphs. The framework proposed in the paper allows a probabilistic analysis of the identifiability in random networks giving a tradeoff between the number of monitors to place and the maximal identifiability.File | Dimensione | Formato | |
---|---|---|---|
Galesi_Vertex-Connectivity_2019.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
349.77 kB
Formato
Adobe PDF
|
349.77 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.