[Dmbu-l] talk Kimon Drakopoulos (MIT) 10/10 10:30 MCS 148
edori at bu.edu
Thu Oct 2 11:20:52 EDT 2014
next weeks talk is by Kimon Drakopolous from MIT. please let me know if
you would like to meet with the speaker. Abstract and title are below.
Hope you can make it to Nicola's talk tomorrow.
Title: Curing epidemics on networks
Abstract: We consider the propagation of a contagion process on a graph
and study the problem of dynamically allocating a fixed curing budget per
time instant over the nodes of the graph. The allocation policy uses
information about the state of each node as well as the network structure.
We provide a lower bound on the extinction time under any such dynamic
allocation policy in terms of a novel measure of "resistance" of the set
of initially infected nodes, and the available budget. For the case where
the whole graph is initially infected (worst case), we provide a sharp
dichotomy among the set of graphs with bounded degree, with regards to the
performance of dynamic curing policies. Specifically, we show that for
graphs that have CutWidth proportional to the number of nodes, it is
impossible to achieve sublinear (in the number of nodes) extinction time
using sublinear budget. On the other hand, for graphs whose CutWidth is a
sublinear function of the number of nodes, we prove the existence of a
policy that achieves sublinear extinction time with sublinear budget.
Finally, we prove that this policy is optimal when the available budget is
More information about the Dmbu-l