Fundamental difference between superblockers and superspreaders in networks

Two important problems regarding spreading phenomena in complex topologies are the optimal selection of node sets either to minimize or maximize the extent of outbreaks. Both problems are nontrivial when a small fraction of the nodes in the network can be used to achieve the desired goal. The minimi...

Descripción completa

Detalles Bibliográficos
Autores principales: Radicchi, Filippo, Castellano, Claudio
Formato: Online Artículo Texto
Lenguaje:English
Publicado: American Physical Society 2017
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7217522/
https://www.ncbi.nlm.nih.gov/pubmed/28208339
http://dx.doi.org/10.1103/PhysRevE.95.012318
_version_ 1783532616845099008
author Radicchi, Filippo
Castellano, Claudio
author_facet Radicchi, Filippo
Castellano, Claudio
author_sort Radicchi, Filippo
collection PubMed
description Two important problems regarding spreading phenomena in complex topologies are the optimal selection of node sets either to minimize or maximize the extent of outbreaks. Both problems are nontrivial when a small fraction of the nodes in the network can be used to achieve the desired goal. The minimization problem is equivalent to a structural optimization. The “superblockers,” i.e., the nodes that should be removed from the network to minimize the size of outbreaks, are those nodes that make connected components as small as possible. “Superspreaders” are instead the nodes such that, if chosen as initiators, they maximize the average size of outbreaks. The identity of superspreaders is expected to depend not just on the topology, but also on the specific dynamics considered. Recently, it has been conjectured that the two optimization problems might be equivalent, in the sense that superblockers act also as superspreaders. In spite of its potential groundbreaking importance, no empirical study has been performed to validate this conjecture. In this paper, we perform an extensive analysis over a large set of real-world networks to test the similarity between sets of superblockers and of superspreaders. We show that the two optimization problems are not equivalent: superblockers do not act as optimal spreaders.
format Online
Article
Text
id pubmed-7217522
institution National Center for Biotechnology Information
language English
publishDate 2017
publisher American Physical Society
record_format MEDLINE/PubMed
spelling pubmed-72175222020-05-13 Fundamental difference between superblockers and superspreaders in networks Radicchi, Filippo Castellano, Claudio Phys Rev E Articles Two important problems regarding spreading phenomena in complex topologies are the optimal selection of node sets either to minimize or maximize the extent of outbreaks. Both problems are nontrivial when a small fraction of the nodes in the network can be used to achieve the desired goal. The minimization problem is equivalent to a structural optimization. The “superblockers,” i.e., the nodes that should be removed from the network to minimize the size of outbreaks, are those nodes that make connected components as small as possible. “Superspreaders” are instead the nodes such that, if chosen as initiators, they maximize the average size of outbreaks. The identity of superspreaders is expected to depend not just on the topology, but also on the specific dynamics considered. Recently, it has been conjectured that the two optimization problems might be equivalent, in the sense that superblockers act also as superspreaders. In spite of its potential groundbreaking importance, no empirical study has been performed to validate this conjecture. In this paper, we perform an extensive analysis over a large set of real-world networks to test the similarity between sets of superblockers and of superspreaders. We show that the two optimization problems are not equivalent: superblockers do not act as optimal spreaders. American Physical Society 2017-01 2017-01-18 /pmc/articles/PMC7217522/ /pubmed/28208339 http://dx.doi.org/10.1103/PhysRevE.95.012318 Text en ©2017 American Physical Society This article is made available via the PMC Open Access Subset for unrestricted re-use and analyses in any form or by any means with acknowledgement of the original source.
spellingShingle Articles
Radicchi, Filippo
Castellano, Claudio
Fundamental difference between superblockers and superspreaders in networks
title Fundamental difference between superblockers and superspreaders in networks
title_full Fundamental difference between superblockers and superspreaders in networks
title_fullStr Fundamental difference between superblockers and superspreaders in networks
title_full_unstemmed Fundamental difference between superblockers and superspreaders in networks
title_short Fundamental difference between superblockers and superspreaders in networks
title_sort fundamental difference between superblockers and superspreaders in networks
topic Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7217522/
https://www.ncbi.nlm.nih.gov/pubmed/28208339
http://dx.doi.org/10.1103/PhysRevE.95.012318
work_keys_str_mv AT radicchifilippo fundamentaldifferencebetweensuperblockersandsuperspreadersinnetworks
AT castellanoclaudio fundamentaldifferencebetweensuperblockersandsuperspreadersinnetworks