Sizing complex networks

Zamora-López, Gorka; Brasselet, Romain

doi:http://dx.doi.org/10.1038/s42005-019-0239-0

Sizing complex networks

License

Citation

Zamora-López G, Brasselet R. Sizing complex networks. Commun Phys. 2019 Nov 14;2:144. DOI: 10.1038/s42005-019-0239-0

Abstract

Among the many features of natural and man-made complex networks the small-world phenomenon is a relevant and popular one. But, how small is a small-world network and how does it compare to others? Despite its importance, a reliable and comparable quantification of the average pathlength of networks has remained an open challenge over the years. Here, we uncover the upper (ultra-long (UL)) and the lower (ultra-short (US)) limits for the pathlength and efficiency of networks. These results allow us to frame their length under a natural reference and to provide a synoptic representation, without the need to rely on the choice for a null-model (e.g., random graphs or ring lattices). Application to empirical examples of three categories (neural, social and transportation) shows that, while most real networks display a pathlength comparable to that of random graphs, when contrasted against the boundaries, only the cortical connectomes prove to be ultra-short.