Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
Comment
. 2019 Jan 29;116(5):1468-1469.
doi: 10.1073/pnas.1817880116. Epub 2019 Jan 10.

Navigability evaluation of complex networks by greedy routing efficiency

Alessandro Muscoloni  1 , Carlo Vittorio Cannistraci  2   3
Affiliations
Comment

Navigability evaluation of complex networks by greedy routing efficiency

Alessandro Muscoloni et al. Proc Natl Acad Sci U S A. .
No abstract available

PubMed Disclaimer

Conflict of interest statement

The authors declare no conflict of interest.

Figures

Fig. 1.
Fig. 1.
(A) Two artificial networks generated in the hyperbolic space using the nonuniform popularity-similarity optimization (nPSO) model (8), with the following parameters: network 1 n = 100, m = 2, T = 0.1, γ = 5, and C = 10; network 2 n = 100, m = 2, T = 0.3, γ = 2.5, and C = 10. N is the network size, m is approximately half of the average node degree, T is the network temperature (inversely related to the clustering), γ is the exponent of the scale-free degree distribution, and C is the number of communities. (B) Bar plots comparing the success ratio, stretch, and GR-score for the two networks; the red arrow indicates which network has a better result for each evaluation measure. Due to the high γ, network 1 is lacking hubs that act as bridges in the navigation between nodes far from each other, and therefore it has a lower success ratio than network 2. However, the successful GR paths of network 1 have a lower stretch than the more numerous ones of network 2, since they are mostly local paths and the higher clustering (lower temperature) facilitates the navigation between nearby nodes. The GR-score provides a unique solution to the conflicting results of the other two measures, suggesting that network 2 has higher navigability, which is reasonable since the success ratio in network 2 is ∼12% higher than in network 1, whereas the stretch decrement of network 1 on network 2 is ∼2%.
See this image and copyright information in PMC

Comment in

Comment on

  • Navigation of brain networks.
    Seguin C, van den Heuvel MP, Zalesky A. Seguin C, et al. Proc Natl Acad Sci U S A. 2018 Jun 12;115(24):6297-6302. doi: 10.1073/pnas.1801351115. Epub 2018 May 30. Proc Natl Acad Sci U S A. 2018. PMID: 29848631 Free PMC article.

References

    1. Kleinberg JM. Navigation in a small world. Nature. 2000;406:845. - PubMed
    1. Boguñá M, Krioukov D, Claffy KC. Navigability of complex networks. Nat Phys. 2008;5:74–80.
    1. Boguñá M, Papadopoulos F, Krioukov D. Sustaining the Internet with hyperbolic mapping. Nat Commun. 2010;1:62. - PubMed
    1. Papadopoulos F, Psomas C, Krioukov D. Network mapping by replaying hyperbolic growth. IEEE/ACM Trans Netw. 2015;23:198–211.
    1. Papadopoulos F, Aldecoa R, Krioukov D. Network geometry inference using common neighbors. Phys Rev E Stat Nonlin Soft Matter Phys. 2015;92:022807. - PubMed

LinkOut - more resources