11:00 am Wednesday, April 10, 2013
Complex Networks Seminar : On Spreading and Detecting Infections by Sanjay Shakkottai (UT Austin, EE dept) in RLM 12.166
In this talk, we study the spread of epidemics (infections) over large networks. In the first part, we study the scenario where the spread is assisted by a small number of external agents: infection sources with bounded spreading power, but whose movement is unrestricted with respect to the underlying network topology. For networks which are ‘spatially constrained’ (e.g., random geometric graphs), we show that the spread of infection can be significantly speeded up even by a few such agents infecting randomly. Further for such networks, we show that simple random, state-oblivious infection-spreading by an external agent is in fact order-wise optimal for dissemination. In the second part, we leverage the network propagation characteristics of epidemics to distinguish between epidemic spreading and "random" failures (e.g., flu vs. allergy, worm attack vs. random computer failures). For instance, a virus that spreads by taking advantage of physical links or user-acquaintance links on a social network can grow explosively if it spreads beyond a critical radius. On the other hand, random infections (that do not take advantage of network structure) have very different propagation characteristics. We address questions like: when can we distinguish between these mechanics of infection? Further, how can this be done efficiently? In this talk, we discuss sufficient conditions and algorithms for different graph topologies, for when it is possible to distinguish between a random model of infection and a spreading epidemic model, with probability of misclassification going to zero.
Submitted by