CNCS Center for Nonlinear and Complex Systems

CNCS Seminar series

Upcoming Seminars:
• Thursday, October 27, 2016, 4:30pm, 119 Physics, Joint Probability and CNCS Seminar
Network Dismantling
Lenka Zdeborova

Many systems of interest can be represented by a network of nodes connected by edges. In many circumstances the existence of a giant component is necessary for the network to fulfill its function. Motivated by the need to understand optimal attack strategies, optimal spread of information or immunization policies, we study the network dismantling problem, i.e. the search of a minimal set of nodes whose removal leaves the network broken into components of sub-extensive size. Building on the statistical mechanics perspective we compute the size of the optimal dismantling set for random networks, propose an efficient dismantling algorithm for general networks that outperforms by a large margin existing strategies, and we provide various insights about the problem.