On identifying the causative network of an epidemic

摘要: The history of infections and epidemics holds famous examples where understanding, containing ultimately treating an outbreak began with understanding its mode spread. key question then, is: which network interactions is the main cause spread? And can we determine causative without any knowledge epidemic, other than identify a minuscule subsample infected nodes? This comes down to diagnostic power information. Specifically, in this paper consider epidemic that spreads on one two networks. At some point time, see small random (perhaps vanishingly fraction) those infected. We derive sufficient conditions networks must have for problem be identifiable. provide efficient algorithm solves hypothesis testing such graphs, characterize regime our succeeds. Finally, show condition need identifiability property fairly mild, particular, satisfied by common graph topologies: grid, Erdos-Renyi graphs.