Distinguishing Infections on Different Graph Topologies

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