On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity
Lokot T, Abramov O, Mehler A (2021)
PLOS ONE 16(11): e0259776.
Zeitschriftenaufsatz
| Veröffentlicht | Englisch
Download
Abramov_PLOS_journal.pone.0259776.pdf
902.22 KB
Einrichtung
Abstract / Bemerkung
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.
Erscheinungsjahr
2021
Zeitschriftentitel
PLOS ONE
Band
16
Ausgabe
11
Art.-Nr.
e0259776
Urheberrecht / Lizenzen
eISSN
1932-6203
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2959064
Zitieren
Lokot T, Abramov O, Mehler A. On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity. PLOS ONE. 2021;16(11): e0259776.
Lokot, T., Abramov, O., & Mehler, A. (2021). On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity. PLOS ONE, 16(11), e0259776. https://doi.org/10.1371/journal.pone.0259776
Lokot, Tatiana, Abramov, Olga, and Mehler, Alexander. 2021. “On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity”. PLOS ONE 16 (11): e0259776.
Lokot, T., Abramov, O., and Mehler, A. (2021). On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity. PLOS ONE 16:e0259776.
Lokot, T., Abramov, O., & Mehler, A., 2021. On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity. PLOS ONE, 16(11): e0259776.
T. Lokot, O. Abramov, and A. Mehler, “On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity”, PLOS ONE, vol. 16, 2021, : e0259776.
Lokot, T., Abramov, O., Mehler, A.: On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity. PLOS ONE. 16, : e0259776 (2021).
Lokot, Tatiana, Abramov, Olga, and Mehler, Alexander. “On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity”. PLOS ONE 16.11 (2021): e0259776.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Name
Abramov_PLOS_journal.pone.0259776.pdf
902.22 KB
Access Level
Open Access
Zuletzt Hochgeladen
2022-01-07T10:18:48Z
MD5 Prüfsumme
f5f3fe193d0bed03b653147001218147
Daten bereitgestellt von European Bioinformatics Institute (EBI)
Zitationen in Europe PMC
Daten bereitgestellt von Europe PubMed Central.
References
Daten bereitgestellt von Europe PubMed Central.
Export
Markieren/ Markierung löschen
Markierte Publikationen
Web of Science
Dieser Datensatz im Web of Science®Quellen
PMID: 34780522
PubMed | Europe PMC
Suchen in