Cargando…
Efficient message passing for cascade size distributions
How big is the risk that a few initial failures of networked nodes amplify to large cascades that endanger the functioning of the system? Common answers refer to the average final cascade size. Two analytic approaches allow its computation: (a) (heterogeneous) mean field approximation and (b) belief...
Autor principal: | |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Nature Publishing Group UK
2019
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6484029/ https://www.ncbi.nlm.nih.gov/pubmed/31024066 http://dx.doi.org/10.1038/s41598-019-42873-9 |
_version_ | 1783414053828296704 |
---|---|
author | Burkholz, Rebekka |
author_facet | Burkholz, Rebekka |
author_sort | Burkholz, Rebekka |
collection | PubMed |
description | How big is the risk that a few initial failures of networked nodes amplify to large cascades that endanger the functioning of the system? Common answers refer to the average final cascade size. Two analytic approaches allow its computation: (a) (heterogeneous) mean field approximation and (b) belief propagation. The former applies to (infinitely) large locally tree-like networks, while the latter is exact on finite trees. Yet, cascade sizes can have broad and multi-modal distributions that are not well represented by their average. Full distribution information is essential to identify likely events and to estimate the tail risk, i.e. the probability of extreme events. We therefore present an efficient message passing algorithm that calculates the cascade size distribution in finite networks. It is exact on finite trees and for a large class of cascade processes. An approximate version applies to any network structure and performs well on locally tree-like networks, as we show with several examples. |
format | Online Article Text |
id | pubmed-6484029 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2019 |
publisher | Nature Publishing Group UK |
record_format | MEDLINE/PubMed |
spelling | pubmed-64840292019-05-13 Efficient message passing for cascade size distributions Burkholz, Rebekka Sci Rep Article How big is the risk that a few initial failures of networked nodes amplify to large cascades that endanger the functioning of the system? Common answers refer to the average final cascade size. Two analytic approaches allow its computation: (a) (heterogeneous) mean field approximation and (b) belief propagation. The former applies to (infinitely) large locally tree-like networks, while the latter is exact on finite trees. Yet, cascade sizes can have broad and multi-modal distributions that are not well represented by their average. Full distribution information is essential to identify likely events and to estimate the tail risk, i.e. the probability of extreme events. We therefore present an efficient message passing algorithm that calculates the cascade size distribution in finite networks. It is exact on finite trees and for a large class of cascade processes. An approximate version applies to any network structure and performs well on locally tree-like networks, as we show with several examples. Nature Publishing Group UK 2019-04-25 /pmc/articles/PMC6484029/ /pubmed/31024066 http://dx.doi.org/10.1038/s41598-019-42873-9 Text en © The Author(s) 2019 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/. |
spellingShingle | Article Burkholz, Rebekka Efficient message passing for cascade size distributions |
title | Efficient message passing for cascade size distributions |
title_full | Efficient message passing for cascade size distributions |
title_fullStr | Efficient message passing for cascade size distributions |
title_full_unstemmed | Efficient message passing for cascade size distributions |
title_short | Efficient message passing for cascade size distributions |
title_sort | efficient message passing for cascade size distributions |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6484029/ https://www.ncbi.nlm.nih.gov/pubmed/31024066 http://dx.doi.org/10.1038/s41598-019-42873-9 |
work_keys_str_mv | AT burkholzrebekka efficientmessagepassingforcascadesizedistributions |