| Abstract: |
Viral spread on large graphs has many real-life applications such asmalware propagation in computer networks and rumor (or misinformation)spread in Twitter-like online social networks. Although viral spreadon large graphs has been intensively analyzed on classical models suchas Susceptible-Infectious-Recovered, there still exits a deficit ofeffective methods in practice to contain epidemic spread once itpasses a critical threshold. Concretely, we consider a random edgeweighted graph $G$ on a fixed degree sequence, where edge weights arei.i.d. non-negative random variables. Given a budget $B>0$, theproblem is to find a subset of edges $E’ subset E(G)$ whose sum ofthe edge weights is at most $B$ and the number of nodes in the largestcomponent of the remaining graph $(V(G),E(G)setminus E’)$ isminimized. We prove bounds on the edge budget: (i) a lower bound on$B$, necessary to break the original graph $G$ into components of atmost constant size $Theta(1)$; (ii) an upper bound on $B$, sufficientsuch that for any choice of removal edges $E’$, with high probabilitythere exist a component of size linear in the number of nodes$Theta(|V(G)|)$. Our bounds depend on the weight of the maximumspanning forest. We furthermore propose and numerically estimateheuristic-based approaches to decompose $G$. Joint work with Mike Molloy and Guanhua Yan |
| Biography: |
Milan Bradonjic is a researcher at Bell Labs, Murray Hill, USA. Priorto that, he was as a postdoctoral research fellow in the AppliedMathematics and Plasma Physics Group, and Center for NonlinearStudies, at Los Alamos National Laboratory. He obtained his Ph.D. atthe University of California, Los Angeles and Dipl. Eng. at theUniversity of Belgrade. His research focuses on random graph theory,and the limiting behavior and percolation of random discretestructures. |
