Back to Search Start Over

Distinguishing Infections on Different Graph Topologies.

Authors :
Milling, Chris
Caramanis, Constantine
Mannor, Shie
Shakkottai, Sanjay
Source :
IEEE Transactions on Information Theory. Jun2015, Vol. 61 Issue 6, p3100-3120. 21p.
Publication Year :
2015

Abstract

The history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00189448
Volume :
61
Issue :
6
Database :
Academic Search Index
Journal :
IEEE Transactions on Information Theory
Publication Type :
Academic Journal
Accession number :
102771763
Full Text :
https://doi.org/10.1109/TIT.2015.2424875