Usando a memória para navegar em redes complexas

Em artigo anterior, apresentamos o problema de navegação em redes complexas e discutimos dois algoritmos baseados em uma busca em profundidade que chamamos aleatório e max-degree. Vimos que estes processos simples conseguem encontrar o destino utilizando rotas curtas, ainda que não sejam as menores possíveis. Nós vimos os processos de busca em redes G(n,m), mas será que temos o mesmo comportamento em redes GWS e GBA? Vamos verificar isto através de um experimento.

Neste experimento, geramos uma rede G(n,m) com 100 nós e 400 enlaces e redes GWS e GBA cujos parâmetros foram escolhidos para que fossem equivalentes à rede G(n,m), ou seja, a mesma quantidade de nós e a mesma densidade da rede aleatória. Assim, a rede GWS tem $k=8$ e $p=0,1$ e a rede GBA tem $\Delta m =4$. 

Para cada par de nós nestas redes, nós calculamos o menor caminho entre o par de nós e realizamos o processo de busca max-degree e o processo de busca aleatório que descrevemos anteriormente. Nós medimos os caminhos encontrados por cada processo de busca por meio do número de saltos e calculamos quantas vezes o caminho encontrado por cada processo é maior do que o menor caminho, fazendo a razão simples entre o tamanho do caminho encontrado pelo respectivo processo de busca e o tamanho do menor caminho.

Observe que o processo de busca aleatório foi realizado apenas uma vez para cada par de nós. No artigo anterior, vimos que o tamanho do caminho encontrado pelo processo de busca aleatória em uma rede pequena, chegou a ser até 9 vezes maior do que o menor caminho. Então, embora haja certa variabilidade no tamanho dos caminhos encontrados pelo processo aleatório para um mesmo par de nós, a decisão de usar apenas um caminho não altera tanto os resultados, já que estamos analisando o comportamento geral dos processos para todos os pares de nós da rede.

Os histogramas a seguir mostram os resultados de cada método em cada modelo de rede estudado. Conforme pode-se notar, os algoritmos se comportam de forma parecida para os diferentes tipos de rede. Na rede GBA, por exemplo, ambos processos de busca apresentam caminhos típicos cujo tamanho é 22 vezes maior do que o menor caminho.

Quando analisamos cada processo em cada rede, vemos que a rede GWS possui uma estrutura que favorece mais os processos de busca do que as demais redes. Um quarto dos caminhos encontrados pelo processo de busca aleatório são até 7 vezes maiores do que os menores caminhos da rede GWS. Já na rede G(n,m) apenas 17% das buscas aleatórias foram menores do que 7 e na rede GBA foi ainda menor, com apenas 12% das buscas.

No caso do processo de busca max-degree na rede GWS, observamos que os caminhos tendem a ser um pouco maiores, pois um quarto das buscas encontram caminhos até 8.2 vezes maiores do que o menor caminho. Na rede G(n,m), 18,5% das buscas foram até 8.2 vezes maiores do que o menor caminho e na rede GBA apenas 6,2% das buscas foram menores do que 8 vezes.

O que estes resultados mostram é que existe a estrutura da rede tem algum impacto sobre os caminhos encontrados pelos processos de busca. A alta aglomeração da rede GWS com muitos enlaces "curtos" (intra-grupo) e poucos enlaces "longos" (inter-grupos) favorece os processos de busca quando a origem e o destino pertencem ao mesmo grupo, principalmente no processo aleatório. Ao entrar em um grupo o processo de busca tem uma alta probabilidade de permanecer no grupo e, explorando os enlaces curtos, localizar o nó destino.

Uma observação a ser feita nos processos que estudamos é que a busca em profundidade não representa bem todo tipo de processo de busca que poderia acontecer em uma rede. Já falamos que ela se adéqua bem à navegação Web. Contudo, nem todos os processos de busca possuem a "memória" destes processos que estudamos. É o caso, por exemplo, do encaminhamento de pacotes em redes de computadores IP. 

Roteadores em redes IP não guardam estado (são stateless) acerca dos pacotes que passam por eles, portanto se um pacote retorna ao roteador (por um erro de roteamento momentâneo) ele tende a ser tratado como um novo pacote e será encaminhado para onde a tabela de roteamento mandar. Por outro lado, o roteamento IP usa informação de toda a rede para montagem de sua tabela de rotas e isso vai contra nossa motivação inicial de tentar enviar dados na rede sem possuir informação global.

Então podemos nos perguntar: existiria uma forma de fazermos encaminhamento na rede sem usar informação global e sem usar memória? Em outras palavras, será que, usando apenas informação local e uma "pitada de sorte", nós conseguimos construir uma forma de navegação tão eficaz quanto estas que conhecemos? Em nosso próximo artigo falaremos sobre o assunto.