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/67ea67cf4ca848e2b041af60da00e63a
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:67ea67cf4ca848e2b041af60da00e63a
record_format	dspace
spelling	oai:doaj.org-article:67ea67cf4ca848e2b041af60da00e63a2021-12-02T20:13:07ZOn the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity.1932-620310.1371/journal.pone.0259776https://doaj.org/article/67ea67cf4ca848e2b041af60da00e63a2021-01-01T00:00:00Zhttps://doi.org/10.1371/journal.pone.0259776https://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, p e0259776 (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/67ea67cf4ca848e2b041af60da00e63a
work_keys_str_mv	AT tatianalokot ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity AT olgaabramov ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity AT alexandermehler ontheasymptoticbehavioroftheaveragegeodesicdistancelandthecompactnesscbofsimpleconnectedundirectedgraphswhoseorderapproachesinfinity
_version_	1718374827584126976

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