Skip to Main content Skip to Navigation
Journal articles

Subgraph detection for average detectability of LTI systems

Nicolas Martin 1 Paolo Frasca 1 Carlos Canudas de Wit 1
1 NECS-POST - Systèmes Commandés en Réseau
Inria Grenoble - Rhône-Alpes, GIPSA-PAD - GIPSA Pôle Automatique et Diagnostic
Abstract : Observation and detection of networked systems aim to reconstruct the evolution of the system based on the measurement of few nodes. In large-scale networks, reconstructing the exact state of each node becomes more complex and in practice it is often superfluous. Reconstructing an aggregated version of the system is often sufficient. In the light of this observation, we consider the notion of average detectability: A system is said to be average detectable if it is possible to reconstruct the average of the subset of its unmeasured nodes. We show here that for a particular type of system, that is negative uniform networks, the average detectability property is reached when the subgraph induced by the unmeasured nodes is regular. Thus, we study the detection of such regular induced subgraph and we propose an algorithm to complete this task. We introduce also the relaxed notion of quasi-regularity ensuring an approximate reconstruction of the average. This paper presents algorithms to detect regular induced subgraphs (RIS) and quasi-regular induced subgraph (q-RIS). We propose an extension to detect multiple quasi-regular induced subgraphs (mq-RIS) in order to reconstruct the average of several subgraphs of the system. Finally we apply our method to the evolution of an epidemic spreading over a simulated contact network over the largest cities in France based on a SIS model.
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Nicolas Martin Connect in order to contact the contributor
Submitted on : Thursday, May 7, 2020 - 6:32:08 PM
Last modification on : Wednesday, November 3, 2021 - 4:26:15 AM


Files produced by the author(s)




Nicolas Martin, Paolo Frasca, Carlos Canudas de Wit. Subgraph detection for average detectability of LTI systems. IEEE Transactions on Network Science and Engineering, IEEE, 2020, 7 (4), pp.2787 - 2798. ⟨10.1109/TNSE.2020.2993691⟩. ⟨hal-02479930v2⟩



Record views


Files downloads