Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

Subgraph detection for average detectability: application to SIS epidemics

Nicolas Martin 1, 2, 3 Paolo Frasca 3 Carlos Canudas de Wit 4
3 NECS-POST - Systèmes Commandés en Réseau
Inria Grenoble - Rhône-Alpes, GIPSA-PAD - GIPSA Pôle Automatique et Diagnostic
4 NECS - Networked Controlled Systems
GIPSA-DA - Département Automatique, Inria Grenoble - Rhône-Alpes
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.
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-02479930
Contributeur : Nicolas Martin Connectez-vous pour contacter le contributeur
Soumis le : vendredi 14 février 2020 - 18:25:40
Dernière modification le : mardi 19 octobre 2021 - 23:22:42
Archivage à long terme le : : vendredi 15 mai 2020 - 18:10:25

Fichier

Partition_To_Detectability_v3....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02479930, version 1

Citation

Nicolas Martin, Paolo Frasca, Carlos Canudas de Wit. Subgraph detection for average detectability: application to SIS epidemics. 2020. ⟨hal-02479930v1⟩

Partager

Métriques

Les métriques sont temporairement indisponibles