Epidemic Spreading With External Agents

DOI10.1109/TIT.2014.2316801zbMATH Open1360.68138arXiv1206.3599OpenAlexW3105297005MaRDI QIDQ2986281FDOQ2986281

Authors: Siddhartha Banerjee, Aditya Gopalan, Abhik Kumar Das, Sanjay Shakkottai

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study epidemic spreading processes in large networks, when the spread is assisted by a small number of external agents: infection sources with bounded spreading power, but whose movement is unrestricted vis-`a-vis the underlying network topology. For networks which are `spatially constrained', we show that the spread of infection can be significantly speeded up even by a few such external agents infecting randomly. Moreover, for general networks, we derive upper-bounds on the order of the spreading time achieved by certain simple (random/greedy) external-spreading policies. Conversely, for certain common classes of networks such as line graphs, grids and random geometric graphs, we also derive lower bounds on the order of the spreading time over all (potentially network-state aware and adversarial) external-spreading policies; these adversarial lower bounds match (up to logarithmic factors) the spreading time achieved by an external agent with a random spreading policy. This demonstrates that random, state-oblivious infection-spreading by an external agent is in fact order-wise optimal for spreading in such spatially constrained networks.

Full work available at URL: https://arxiv.org/abs/1206.3599

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Internet topics (68M11)

Cited In (6)

This page was built for publication: Epidemic Spreading With External Agents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986281)