New article in PLOS ONE

The following new publication was accepted in the Journal:

PLOS ONE

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

Total: 1

• 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, iss. 11, pp. 1-13, 2021.
  [Abstract] [BibTeX]

  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.

  @article{Lokot:Abramov:Mehler:2021,
      doi = {10.1371/journal.pone.0259776},
      author = {Lokot, Tatiana and Abramov, Olga and Mehler, Alexander},
      journal = {PLOS ONE},
      publisher = {Public Library of Science},
      title = {On the asymptotic behavior of the average geodesic distance L and the compactness CB of simple connected undirected graphs whose order approaches infinity},
      year = {2021},
      month = {11},
      volume = {16},
      url = {https://doi.org/10.1371/journal.pone.0259776},
      pages = {1-13},
      abstract = {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.},
      number = {11}
  }