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...
Autores principales: | , , |
---|---|
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 |