Room 1037 Emerging Technology Building (ETB)
Dr. Sanjay Shakkottai
Dept. of Electrical & Computer Engr./Univ. of Texas at Austin
Abstract: 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.
1. “Epidemic Spreading with External Agents,” A. Gopalan, S. Banerjee,
A. Das and S. Shakkottai, Technical Report. Earlier version appeared
in the Proceedings of IEEE Infocom, Shanghai, China, 2011. Available
2. “Network Forensics: Random Infection vs. Spreading Epidemic,” C.
Milling, C. Caramanis, S. Mannor and S. Shakkottai, Proc. of ACM
Sigmetrics, London, UK, June 2012. Available at:
Biography: Sanjay Shakkottai received his Ph.D. from the ECE
Department at the University of Illinois at Urbana-Champaign in 2002.
He is with The University of Texas at Austin, where he is currently a
Professor in the Department of Electrical and Computer Engineering,
and the Associate Director of Wireless Networking and Communications
Group (WNCG). He received the NSF CAREER award in 2004. His current
research interests include network architectures, algorithms and
performance analysis for wireless networks, and algorithms for
learning and inference over complex networks.