Cargando…
Configuration models as an urn problem
A fundamental issue of network data science is the ability to discern observed features that can be expected at random from those beyond such expectations. Configuration models play a crucial role there, allowing us to compare observations against degree-corrected null-models. Nonetheless, existing...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Nature Publishing Group UK
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8239003/ https://www.ncbi.nlm.nih.gov/pubmed/34183694 http://dx.doi.org/10.1038/s41598-021-92519-y |
_version_ | 1783714993330454528 |
---|---|
author | Casiraghi, Giona Nanumyan, Vahan |
author_facet | Casiraghi, Giona Nanumyan, Vahan |
author_sort | Casiraghi, Giona |
collection | PubMed |
description | A fundamental issue of network data science is the ability to discern observed features that can be expected at random from those beyond such expectations. Configuration models play a crucial role there, allowing us to compare observations against degree-corrected null-models. Nonetheless, existing formulations have limited large-scale data analysis applications either because they require expensive Monte-Carlo simulations or lack the required flexibility to model real-world systems. With the generalized hypergeometric ensemble, we address both problems. To achieve this, we map the configuration model to an urn problem, where edges are represented as balls in an appropriately constructed urn. Doing so, we obtain the generalized hypergeometric ensemble of random graphs: a random graph model reproducing and extending the properties of standard configuration models, with the critical advantage of a closed-form probability distribution. |
format | Online Article Text |
id | pubmed-8239003 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | Nature Publishing Group UK |
record_format | MEDLINE/PubMed |
spelling | pubmed-82390032021-07-06 Configuration models as an urn problem Casiraghi, Giona Nanumyan, Vahan Sci Rep Article A fundamental issue of network data science is the ability to discern observed features that can be expected at random from those beyond such expectations. Configuration models play a crucial role there, allowing us to compare observations against degree-corrected null-models. Nonetheless, existing formulations have limited large-scale data analysis applications either because they require expensive Monte-Carlo simulations or lack the required flexibility to model real-world systems. With the generalized hypergeometric ensemble, we address both problems. To achieve this, we map the configuration model to an urn problem, where edges are represented as balls in an appropriately constructed urn. Doing so, we obtain the generalized hypergeometric ensemble of random graphs: a random graph model reproducing and extending the properties of standard configuration models, with the critical advantage of a closed-form probability distribution. Nature Publishing Group UK 2021-06-28 /pmc/articles/PMC8239003/ /pubmed/34183694 http://dx.doi.org/10.1038/s41598-021-92519-y Text en © The Author(s) 2021 https://creativecommons.org/licenses/by/4.0/Open AccessThis 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 licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence 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 licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . |
spellingShingle | Article Casiraghi, Giona Nanumyan, Vahan Configuration models as an urn problem |
title | Configuration models as an urn problem |
title_full | Configuration models as an urn problem |
title_fullStr | Configuration models as an urn problem |
title_full_unstemmed | Configuration models as an urn problem |
title_short | Configuration models as an urn problem |
title_sort | configuration models as an urn problem |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8239003/ https://www.ncbi.nlm.nih.gov/pubmed/34183694 http://dx.doi.org/10.1038/s41598-021-92519-y |
work_keys_str_mv | AT casiraghigiona configurationmodelsasanurnproblem AT nanumyanvahan configurationmodelsasanurnproblem |