Ant Colonies And Algorithms

A new analysis of ant colony behavior could help develop better algorithms for network communication.

Ants base their population-density estimates on the frequency with which they bump into each other while exploring their environments. New research shows that this is actually a good practice. If we translate this into human terms, it’s rather intuitive that if a bunch of people is randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density.

Since ants are apparently extremely good at estimating the concentration of other ants in their environment, this could be applied to the analysis of social networks and collective decision making among robot swarms.

The researchers characterize an ant’s environment as a grid, and their population-density estimates as “random walk”, which they compare to random sampling. Here, cells are selected from the grid at random and the number of ants counted. Interestingly, the accuracy of both approaches increases with each additional sample, but the random walk converges on the true population density almost as quickly as random sampling does.

Why is this important? Because, if you wanted to write an algorithm to analyze an online social network your best bet would be using random walk. Let’s say you wanted to estimate what fraction of the network self-describes as Republican. Since there’s no publicly available list of the network’s members, the only way you could explore it is to pick an individual member and start tracing connections.

In conclusion, algorithms for network communications could greatly benefit from using random walk.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s