[Dmbu-l] Talk by Kimon Drakopoulus (MIT) Firday 10/10 10:30 MCS 148

Dora Erdos edori at bu.edu
Tue Oct 7 10:00:16 EDT 2014


Hi All,

this 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.


Best,
Dora

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 sufficiently
high.



More information about the Dmbu-l mailing list