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...

Descripción completa

Detalles Bibliográficos
Autores principales: Casiraghi, Giona, Nanumyan, Vahan
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