Joint Probability and CNCS Seminar
Thursday, October 27, 2016, 4:30pm, 119 Physics
Lenka Zdeborova
Network Dismantling
Abstract:
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. [video]

Generated at 6:06pm Thursday, March 28, 2024 by Mcal.   Top * Reload * Login