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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Public Library of Science (PLoS)
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/fd88fb4905ae4d5a902bff33939a738d |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|