On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity

The average geodesic distance L Newman (2003) and the compactness CB 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 CB(G), subject to the condit...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Tatiana Lokot, Olga Abramov, Alexander Mehler
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/fd88fb4905ae4d5a902bff33939a738d
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:fd88fb4905ae4d5a902bff33939a738d
record_format	dspace
spelling	oai:doaj.org-article:fd88fb4905ae4d5a902bff33939a738d2021-11-25T05:54:23ZOn the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity1932-6203https://doaj.org/article/fd88fb4905ae4d5a902bff33939a738d2021-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC8592497/?tool=EBIhttps://doaj.org/toc/1932-6203The average geodesic distance L Newman (2003) and the compactness CB 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 CB(G), subject to the condition that their order \|V(G)\| approaches infinity. We prove that the limit of L(G)/n and CB(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 (CB(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.Tatiana LokotOlga AbramovAlexander MehlerPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 16, Iss 11 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Tatiana Lokot Olga Abramov Alexander Mehler On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity
description	The average geodesic distance L Newman (2003) and the compactness CB 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 CB(G), subject to the condition that their order \|V(G)\| approaches infinity. We prove that the limit of L(G)/n and CB(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 (CB(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	article
author	Tatiana Lokot Olga Abramov Alexander Mehler
author_facet	Tatiana Lokot Olga Abramov Alexander Mehler
author_sort	Tatiana Lokot
title	On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity
title_short	On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity
title_full	On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity
title_fullStr	On the asymptotic behavior of the average geodesic distance L and the compactness CB 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 CB of simple connected undirected graphs whose order approaches infinity
title_sort	on the asymptotic behavior of the average geodesic distance l and the compactness cb of simple connected undirected graphs whose order approaches infinity
publisher	Public Library of Science (PLoS)
publishDate	2021
url	https://doaj.org/article/fd88fb4905ae4d5a902bff33939a738d
work_keys_str_mv	AT tatianalokot ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity AT olgaabramov ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity AT alexandermehler ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity
_version_	1718414438784040960

On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity

Ejemplares similares