Frogs resolve computing issues

When male Japanese tree frogs sing at the same time, the females cannot differentiate between them in order to choose the best one. Therefore, the would-be suitors have come to an agreement and sing one by one. This natural lyrical desynchronisation has inspired the development of computational algorithms which can be used to design wireless systems and analyse social networks such as Facebook or Twitter.

It is now increasingly usual for specialists in the computing sector to turn to nature when trying to resolve optimisation issues. Ant colonies and the nervous system of the fruit fly have inspired the development of robust algorithms that, just like systems in nature, can adapt well to the circumstances and to potential problems.

Researchers from the University of the Basque Country (UPV/EHU) and the Technical University of Catalonia (UPC) have now turned their attention to an amphibian in order to come up with new computational algorithms: the Japanese tree frog (Hyla japonica).

The males of this species sing to attract their female counterparts, which are able to identify the source of the call and pinpoint the location of the would-be suitor. The problem arises when two or more males are too close together and sing at the same time. If this happens, the females get confused and cannot tell where the calls are coming from.

For this reason, the males have had to learn to desynchronise their singings, meaning that they don't sing at the same time. This allows the females to differentiate between them, and thus choose the most talented one. "This process is a great example of self-organisation in nature, which has allowed us to develop bio-inspired algorithms," explains Christian Blum, Ikerbasque Professor at the UPV/EHU.

The team has used this mathematical tool to resolve computing issues associated with graphs, set of nodes joined together by links which represent their interrelationships. For example, metro networks or the friendships between people could be represented in graphs.

Several years ago, partially the same researchers used these algorithms to colour graphs, a technique with possible applications in the field of wireless networks. Now, according to a study published in the journal 'Swarm Intelligence', they have been used to detect something called 'independent set of nodes', meaning those which are not directly connected within the graph.

"This has a number of vital applications in communication networks, such as in the formation of wireless backbone networks," Blum suggests, "but also in social networks such as Facebook and Twitter, since it allows for structural analysis and for the detection of independent communities within these networks."

In this way, it is possible to track down inconspicuous or inactive users, detect tight-knit communities that don't interact with anyone else, discover popular or well-known individuals within the network, or find users who would be willing to connect in order to improve relations between specific communities. "All these issues can be translated into mathematical problems, which can then be solved on a graph representing the network," Blum points out.

According to the authors, the results of these new algorithms "are excellent, the best ever up until now, and have done significantly more than other algorithms, such as those inspired by the nervous system of the Drosophila fly, were able to accomplish."