Programa busca conexões inspirado em rede social das formigas

Redação do Site Inovação Tecnológica - 07/06/2012

As formigas são capazes de traçar rotas diretas até as fontes de alimento sem precisar seguir todos os rastros de feromônio deixados enquanto as batedoras procuravam pela comida.
[Imagem: U3CM]

Amigos, entregas e neurônios

Cientistas espanhóis criaram um algoritmo que usa o comportamento das formigas para encontrar conexões entre membros de uma rede social.

Um dos desafios para criar um programa desse tipo é que as redes sociais são gigantescas, exigindo um processamento muito pesado. E quem busca as conexões de alguém quer a resposta muito rapidamente.

Quando expressaram o problema em termos da teoria dos grafos, Jessica Rivero e seus colegas da Universidade Carlos III descobriram que o esforço poderia valer a pena porque a solução teria uma utilização muito ampla.

Por exemplo, um programa eficiente desse tipo permite traçar rotas para caminhões de entrega, descobrir caminhos mais curtos em navegadores GPS, saber se duas palavras estão relacionadas de alguma forma - ou descobrir as conexões entre pessoas nas redes sociais.

Além do interesse ou da curiosidade dos próprios usuários, as conexões nas redes sociais têm sido cada vez mais usadas como instrumento de pesquisa pela antropologia e pela psicologia. O mesmo mecanismo é usado pela neurociência para o estudo das conexões entre os neurônios.

Múltiplas trilhas

Cada indivíduo, ou cada ponto de entrega, ou cada destino, são representados como pontos de um grafo - grafo é uma representação que usa pontos interligados por retas para mostrar as interconexões de uma rede.

Percorrer todas as rotas possíveis para encontrar as ligações é um problema que cresce exponencialmente conforme se avança pelos nós individuais, tornando essa técnica de força bruta inviável em termos computacionais quando os grafos têm mais do que algumas centenas de nós.

Os pesquisadores espanhóis foram buscar inspiração nas formigas, que constroem trilhas a partir do seu formigueiro para encontrar comida.

Eles explicam que, além da trilha química que as formigas traçam usando seu feromônio, quando estão buscando alimento, elas deixam outros sinais químicos, equivalentes do "cheiro da comida".

E isto permite que a colônia localize a fonte de alimento muito mais rapidamente e de forma praticamente direta, sem ter que percorrer todos os múltiplos caminhos que as batedoras usaram quando estavam procurando o alimento.

Algoritmos inspirados em insetos

Embora muitos outros programadores já tenham se inspirado no comportamento de insetos para desenvolver algoritmos de busca, a inclusão desses sinalizadores adicionais deu resultados estupendos.

"Os resultados iniciais mostram que a aplicação desse algoritmo às redes sociais gera uma resposta ótima em um tempo muito curto, na casa das dezenas de milissegundos," contou Jessica.

Segundo ela, o principal ganho é que, imitando as trilhas multiplamente sinalizadas das formigas, torna-se possível evitar a modificação do grafo para a busca, reduzindo muito o tempo de processamento.

Mais tópicos