Subgraph detection for average detectability: application to SIS epidemics

Nicolas Martin (1, 2, 3) , Paolo Frasca (3) , Carlos Canudas de Wit (4)

1 GIPSA-lab - Grenoble Images Parole Signal Automatique
2 GIPSA-DA - Département Automatique
3 NECS-POST - Systèmes Commandés en Réseau
4 NECS - Networked Controlled Systems

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.

Mots clés: Regular induced subgraph; Observability; Detectability; Algorithmic; Network epidemics

Domaines: Réseaux sociaux et d'information [cs.SI]; Réseaux et télécommunications [cs.NI]; Algorithme et structure de données [cs.DS]

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