[Dmbu-l] talk Kimon Drakopoulos (MIT) 10/10 10:30 MCS 148

Dora Erdos edori at bu.edu
Thu Oct 2 11:20:52 EDT 2014


Hi All,

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.

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