Cargando…

On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity

The average geodesic distance L Newman (2003) and the compactness C(B) Botafogo (1992) are important graph indices in applications of complex network theory to real-world problems. Here, for simple connected undirected graphs G of order n, we study the behavior of L(G) and C(B)(G), subject to the co...

Descripción completa

Detalles Bibliográficos
Autores principales: Lokot, Tatiana, Abramov, Olga, Mehler, Alexander
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8592497/
https://www.ncbi.nlm.nih.gov/pubmed/34780522
http://dx.doi.org/10.1371/journal.pone.0259776
_version_ 1784599475190235136
author Lokot, Tatiana
Abramov, Olga
Mehler, Alexander
author_facet Lokot, Tatiana
Abramov, Olga
Mehler, Alexander
author_sort Lokot, Tatiana
collection PubMed
description The average geodesic distance L Newman (2003) and the compactness C(B) Botafogo (1992) are important graph indices in applications of complex network theory to real-world problems. Here, for simple connected undirected graphs G of order n, we study the behavior of L(G) and C(B)(G), subject to the condition that their order |V(G)| approaches infinity. We prove that the limit of L(G)/n and C(B)(G) lies within the interval [0;1/3] and [2/3;1], respectively. Moreover, for any not necessarily rational number β ∈ [0;1/3] (α ∈ [2/3;1]) we show how to construct the sequence of graphs {G}, |V(G)| = n → ∞, for which the limit of L(G)/n (C(B)(G)) is exactly β (α) (Theorems 1 and 2). Based on these results, our work points to novel classification possibilities of graphs at the node level as well as to the information-theoretic classification of the structural complexity of graph indices.
format Online
Article
Text
id pubmed-8592497
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-85924972021-11-16 On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity Lokot, Tatiana Abramov, Olga Mehler, Alexander PLoS One Research Article The average geodesic distance L Newman (2003) and the compactness C(B) Botafogo (1992) are important graph indices in applications of complex network theory to real-world problems. Here, for simple connected undirected graphs G of order n, we study the behavior of L(G) and C(B)(G), subject to the condition that their order |V(G)| approaches infinity. We prove that the limit of L(G)/n and C(B)(G) lies within the interval [0;1/3] and [2/3;1], respectively. Moreover, for any not necessarily rational number β ∈ [0;1/3] (α ∈ [2/3;1]) we show how to construct the sequence of graphs {G}, |V(G)| = n → ∞, for which the limit of L(G)/n (C(B)(G)) is exactly β (α) (Theorems 1 and 2). Based on these results, our work points to novel classification possibilities of graphs at the node level as well as to the information-theoretic classification of the structural complexity of graph indices. Public Library of Science 2021-11-15 /pmc/articles/PMC8592497/ /pubmed/34780522 http://dx.doi.org/10.1371/journal.pone.0259776 Text en © 2021 Lokot et al https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Lokot, Tatiana
Abramov, Olga
Mehler, Alexander
On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity
title On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity
title_full On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity
title_fullStr On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity
title_full_unstemmed On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity
title_short On the asymptotic behavior of the average geodesic distance L and the compactness C(B) of simple connected undirected graphs whose order approaches infinity
title_sort on the asymptotic behavior of the average geodesic distance l and the compactness c(b) of simple connected undirected graphs whose order approaches infinity
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8592497/
https://www.ncbi.nlm.nih.gov/pubmed/34780522
http://dx.doi.org/10.1371/journal.pone.0259776
work_keys_str_mv AT lokottatiana ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity
AT abramovolga ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity
AT mehleralexander ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity