•New

It is increasingly common to use nature to solve the optimisation problems faced by experts in the field of computing. In a recent joint research project, Maria Jose Blesa, a professor at the Department of Computer Science of the Universitat Politècnica de Catalunya (UPC), Christian Blum, a professor at the University of the Basque Country (UPV/EHU) and a visiting professor at the UPC, and Borja Calvo, also a professor at the UPV/EHU, have used the Japanese tree frog (Hyla japonica) to create new computational algorithms.

The male of the species sings to attract the female, who recognise the source of the call and locates the suitor. A problem arises, however, when two or more males who are close together sing at the same time. The female gets confused and cannot determine where the call she is interested in is coming from.

For this reason, males have had to learn how to unsync their song, i.e. to avoid singing at the same time, so that the females can distinguish between them and choose the best partner. "This process is a good example of self-organisation and it has helped us to develop bio-inspired algorithms," explains Christian Blum.

The team used this mathematical tool to solve computing problems related to graphs, which are a set of nodes joined in a graphic manner that represents their relations. For example, graphs can be used to represent an underground train network or friendships between people.
A few years ago, researchers used these algorithms to colour graphs, a technique that can be applied in wireless network environments. Today, according to the study published in the journal Swarm Intelligence, the algorithms are used to detect so-called 'independent sets of nodes', which are those that are not linked directly within the graph.

"This has very important applications in communication networks; for example, in the formation of backbone networks and wireless backbone networks, but also in social networks such as Facebook and Twitter, because it enables their structure to be analysed and independent communities to be detected within a social network," adds Blum.

In this way, users whose participation or visibility is limited can be located; very closed communities that do not interact with others can be detected; popular, well-connected figures can be discovered; and users who should be connected to increase relations between certain communities can be identified. "All these issues can be translated into mathematical problems that can be solved on a graph representing the network," says the UPC's visiting professor.

According to the authors, the results of the new algorithms "are excellent and have become the best so far, significantly exceeding the results achieved by other algorithms such as those inspired by the nervous system of the Drosophila fly".