The small-world property is a property of networks in which, despite a large number of nodes, it is possible to find short communication paths between them.
Discovered in the field of social sciences in the 1960s, the phenomenon known as small-world has fascinated popular culture and science for decades. It arose from the observation that in the world, any two people are connected by a short chain of social ties.
A network, whether natural (neural or social) or artificial (communication or transport systems) is an ordered set of elements connected to each other through various methods that share information. The small-world property is a property of networks in which, despite a large number of nodes, it is possible to find short communication paths between them. In recent decades it has been proved that both in natural and artificial systems, many real networks are also small-world. But, are all small-world networks small, and how do they compare to others?
In the physical world we evaluate and compare the size of objects by contrasting them to a common reference, usually a standard metric system defined and agreed by the community. In the case of complex networks, the difference is that every network constitutes its own metric space. Thus, the question of whether a network is smaller or larger than another implies the comparison of two different spaces with each other, rather than the more familiar situation in which two objects are contrasted within the space they share.
Despite the existing variety of small-world networks, it still remains a challenge to make a reliable and comparable measurement of their average length.
The main result of a study published in Nature Communications Physics on 14 November is "the identification of the lower and upper boundaries for the average pathlength and global efficiency for (di)graphs of arbitrary number of nodes and links", assert Gorka Zamora-Lopez, a researcher at the Center for Brain and Cognition (CBC) at the Department of Information and Communication Technologies (DTIC) and Romain Brasselet, a researcher at the International School for Advanced Studies (SISSA) in Trieste (Italy), authors of the work.
"We can now assess the average pathlength of a network--of a given size and density--by evaluating how much it deviates from the smallest and the largest pathlength it could possibly take", Zamora López and Brasselet comment.
These results allow characterizing the length of a network under a natural reference and provide a synoptic representation, without the need to choose between models generated randomly (random graphs) as had been the case to date. In other words, "this theoretical framework allows us to evaluate both empirical networks and graph models together under the same reference framework. While the pathlength of these constructions is comparable, their dynamic properties may differ significantly", they add.
The implications of these results transcend the purely structural study of networks. Applying this theoretical framework 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 upper and lower boundaries, only the neural networks, i.e., the cortical connectomes, prove to be ultra-short.
The authors conclude that network optimization problems involve the maximization of a variety of parameters. The results they have obtained are the solutions to the simplest case with a minimal set of constraints. These solutions can serve as the starting point for studying more complex problems which include additional constraints beyond the number of nodes and links.