文章基本信息

标题：Network dismantling
本地全文：下载
作者：Alfredo Braunstein ; Luca Dall’Asta ; Guilhem Semerjian 等
期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2016
卷号：113
期号：44
页码：12368-12373
DOI：10.1073/pnas.1605083113
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：We study the network dismantling problem, which consists of determining a minimal set of vertices in which removal leaves the network broken into connected components of subextensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices, leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading, we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective, we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide additional insights into the dismantling problem, concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well-performing nodes.
关键词：graph fragmentation ; message passing ; percolation ; random graphs ; influence maximization