BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:74@lincs.fr
DTSTART;TZID=Europe/Paris:20151028T140000
DTEND;TZID=Europe/Paris:20151028T150000
DTSTAMP:20170313T170939Z
URL:https://www.lincs.fr/events/trimming-sparse-random-graphs-bounds-algor
 ithms-and-experiments/
SUMMARY:Trimming Sparse Random Graphs: Bounds\, Algorithms\, and
 Experiments
DESCRIPTION:\n\n\nAbstract:\nViral 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&gt\;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\n\n\nBiography:\nMilan 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.\n\n\n
CATEGORIES:Seminars,Youtube
LOCATION:LINCS Meeting Room 40\, 23\, avenue d'Italie\, Paris\, 75013\,
 France
GEO:48.8283983;2.3568972000000485
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23\, avenue d'Italie\,
 Paris\, 75013\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS Meeting Room
 40:geo:48.8283983,2.3568972000000485
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20151025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR