How small is a small-world network?

December 04, 2019

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.

Universitat Pompeu Fabra - Barcelona

Related Communication Articles from Brightsurf:

Video is not always effective in science communication
What we can learn for online public relations: - Keep the information concise so that one can go thorough it within about 1 minute.

Ultraviolet communication to transform Army networks
Of ever-increasing concern for operating a tactical communications network is the possibility that a sophisticated adversary may detect friendly transmissions.

Adding noise for completely secure communication
How can we protect communications against 'eavesdropping' if we don't trust the devices used in the process?

How serotonin balances communication within the brain
Our brain is steadily engaged in soliloquies. These internal communications are usually also bombarded with external sensory events.

Breaking the communication code
Ever wonder how mice talk to each other. We don't have a dictionary quite yet, but UD neuroscientist Josh Neunuebel and his lab have linked mice chatter (their ultrasonic vocalizations) with specific behaviors.

A new twist on quantum communication in fiber
New research done at the University of the Witwatersrand in Johannesburg, South Africa, and Huazhang University of Science and Technology in Wuhan, China, has exciting implications for secure data transfer across optical fiber networks.

Study traces evolution of acoustic communication
A study tracing acoustic communication across the tree of life of land-living vertebrates reveals that the ability to vocalize goes back hundreds of millions of years, is associated with a nocturnal lifestyle and has remained stable.

Should preschool writing be more communication and less ABCs?
Writing instruction in early education should be about more than letter formation and penmanship, argue Michigan State University researchers who found preschool teachers don't often encourage writing for communication purposes.

Trump's Twitter communication style shifted over time based on varying communication goals
The linguistic and discursive style of Donald Trump's tweets varied systematically before, during, and after the 2016 presidential campaign, depending on the communicative goals of Trump and his team, according to a study published Sept.

Intercultural communication crucial for engineering education
In an increasingly connected world it helps to engage with other cultures without prejudice or assumption.

Read More: Communication News and Communication Current Events is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to