Seminar by L. Dall'Asta- Feb. 1, 2017, at 14.00 hrs @ SISSA

[Quantitative Life Sciences]

 Speaker:
 Dr. Luca Dall'Asta (Politecnico di Torino)


 Title: Network dismantling

 Wednesday, Feb. 1, 2017 @ 02:00 p.m.

 Venue: SISSA, Via Bonomea, 265, 1st floor, room 128-129 (cinema room)


 Abstract:

 Network dismantling consists of determining a minimal set of vertices
whose removal leaves the network broken into connected components of
sub-extensive size. I will show that for a large class of random graphs,
this problem is tightly related to the decycling problem (the removal of
vertices, leaving an acyclic graph), and that the latter can be
effectively and efficiently solved using algorithmic methods from the
statistical mechanics of disordered systems. The results reveal that the
problem is intrinsically collective and optimal dismantling sets cannot
be viewed as a collection of individually well-performing nodes as
usually suggested by most heuristic (greedy, centrality-based) methods.
 Finally, I will discuss in detail the idea behind the algorithmic
technique, that can be used to tackle other         interesting inference
and optimization problems involving epidemic-like dynamical processes on
graphs.

Reference:
 A. Braunstein, L. Dall'Asta, G. Semerjian, L. Zdeborova, PNAS, 113(44)
12368-12373 (2016).

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Attached Message Part.txt
URL: <https://lists.ictp.it/pipermail/science-ts/attachments/20170127/1eadc671/attachment.txt>