Cargando…

From the betweenness centrality in street networks to structural invariants in random planar graphs

The betweenness centrality, a path-based global measure of flow, is a static predictor of congestion and load on networks. Here we demonstrate that its statistical distribution is invariant for planar networks, that are used to model many infrastructural and biological systems. Empirical analysis of...

Descripción completa

Detalles Bibliográficos
Autores principales: Kirkley, Alec, Barbosa, Hugo, Barthelemy, Marc, Ghoshal, Gourab
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Nature Publishing Group UK 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6021391/
https://www.ncbi.nlm.nih.gov/pubmed/29950619
http://dx.doi.org/10.1038/s41467-018-04978-z
_version_ 1783335460322410496
author Kirkley, Alec
Barbosa, Hugo
Barthelemy, Marc
Ghoshal, Gourab
author_facet Kirkley, Alec
Barbosa, Hugo
Barthelemy, Marc
Ghoshal, Gourab
author_sort Kirkley, Alec
collection PubMed
description The betweenness centrality, a path-based global measure of flow, is a static predictor of congestion and load on networks. Here we demonstrate that its statistical distribution is invariant for planar networks, that are used to model many infrastructural and biological systems. Empirical analysis of street networks from 97 cities worldwide, along with simulations of random planar graph models, indicates the observed invariance to be a consequence of a bimodal regime consisting of an underlying tree structure for high betweenness nodes, and a low betweenness regime corresponding to loops providing local path alternatives. Furthermore, the high betweenness nodes display a non-trivial spatial clustering with increasing spatial correlation as a function of the edge-density. Our results suggest that the spatial distribution of betweenness is a more accurate discriminator than its statistics for comparing  static congestion patterns and  its evolution across cities as demonstrated by analyzing 200 years of street data for Paris.
format Online
Article
Text
id pubmed-6021391
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Nature Publishing Group UK
record_format MEDLINE/PubMed
spelling pubmed-60213912018-06-29 From the betweenness centrality in street networks to structural invariants in random planar graphs Kirkley, Alec Barbosa, Hugo Barthelemy, Marc Ghoshal, Gourab Nat Commun Article The betweenness centrality, a path-based global measure of flow, is a static predictor of congestion and load on networks. Here we demonstrate that its statistical distribution is invariant for planar networks, that are used to model many infrastructural and biological systems. Empirical analysis of street networks from 97 cities worldwide, along with simulations of random planar graph models, indicates the observed invariance to be a consequence of a bimodal regime consisting of an underlying tree structure for high betweenness nodes, and a low betweenness regime corresponding to loops providing local path alternatives. Furthermore, the high betweenness nodes display a non-trivial spatial clustering with increasing spatial correlation as a function of the edge-density. Our results suggest that the spatial distribution of betweenness is a more accurate discriminator than its statistics for comparing  static congestion patterns and  its evolution across cities as demonstrated by analyzing 200 years of street data for Paris. Nature Publishing Group UK 2018-06-27 /pmc/articles/PMC6021391/ /pubmed/29950619 http://dx.doi.org/10.1038/s41467-018-04978-z Text en © The Author(s) 2018 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
Kirkley, Alec
Barbosa, Hugo
Barthelemy, Marc
Ghoshal, Gourab
From the betweenness centrality in street networks to structural invariants in random planar graphs
title From the betweenness centrality in street networks to structural invariants in random planar graphs
title_full From the betweenness centrality in street networks to structural invariants in random planar graphs
title_fullStr From the betweenness centrality in street networks to structural invariants in random planar graphs
title_full_unstemmed From the betweenness centrality in street networks to structural invariants in random planar graphs
title_short From the betweenness centrality in street networks to structural invariants in random planar graphs
title_sort from the betweenness centrality in street networks to structural invariants in random planar graphs
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6021391/
https://www.ncbi.nlm.nih.gov/pubmed/29950619
http://dx.doi.org/10.1038/s41467-018-04978-z
work_keys_str_mv AT kirkleyalec fromthebetweennesscentralityinstreetnetworkstostructuralinvariantsinrandomplanargraphs
AT barbosahugo fromthebetweennesscentralityinstreetnetworkstostructuralinvariantsinrandomplanargraphs
AT barthelemymarc fromthebetweennesscentralityinstreetnetworkstostructuralinvariantsinrandomplanargraphs
AT ghoshalgourab fromthebetweennesscentralityinstreetnetworkstostructuralinvariantsinrandomplanargraphs