Navegando em Redes Complexas

A navegação é um processo de busca onde uma mensagem encontra seu caminho de uma fonte até seu destino usando somente informação local, tal como o grau, ou outra medida de centralidade.

O problema proposto é: dado um nó de destino e a presença de informação local apenas, selecionar um enlace que possa levar até o nó destino. Tal decisão é feita em cada nó visitado, utilizando apenas informação localmente disponível. No problema de navegação, cada salto não deve ter qualquer informação da existência do nó destino, a não ser que este seja ele mesmo.

Note que este método difere do encaminhamento/roteamento que ocorre nas redes de computadores. Nestas redes, utiliza-se o menor caminho, o qual é calculado por meio de informação global. Aqui se enquadram tanto os algoritmos estado de enlace que trocam globalmente informações locais da rede, quanto os algoritmos do tipo vetor de distância que trocam localmente informações globais da rede.

Diversos processos podem ser usados neste problema. Neste artigo, avaliaremos dois tipos: aleatório e max-degree. Lembre-se que temos dois nós, um de origem e outro de destino.

Na busca aleatória. Partindo do nó de origem iremos realizar uma busca em profundidade. Assim, quando chegarmos em um nó qualquer, checaremos se ele é o nó de destino. Caso seja, a busca termina; caso não seja, deve-se escolher aleatoriamente um nó vizinho para continuar a busca (perceba que o nó de chegada ao nó atual não pode ser escolhido embora seja vizinho). Se de um nó não houve nenhum outro nó a visitar deve-se retornar ao nó de chegada e procurar outro caminho. Note que esta busca sempre vai terminar encontrando o nó de destino (desde que a rede seja conexa), ainda que possa tomar muitos saltos.

Abaixo vemos uma rede G(n,m) com 20 nós e 50 enlaces. Os nós 16 e 17 foram escolhidos aleatoriamente como a origem e o destino, respectivamente, do processo de navegação que vamos realizar. Observe que o menor caminho entre estes nós é formado pelos nós 16, 1 e 17, tendo portanto 2 saltos.

O processo de navegação aleatório obtém diferentes caminhos como 16, 11, 1 e 17 ou 16, 1, 14, 6, 7, 12, 9, 11 e 17 (sugiro acompanhar no grafo acima os caminhos para verificar a conectividade). Portanto usando esta estratégia é possível chegarmos ao destino, mesmo que seja preciso um elevado número de saltos. Contudo, nem sempre obtemos caminhos muito longos.

O histograma abaixo mostra o tamanho dos caminhos aleatórios encontrados em uma base de mais de 6000 caminhos. Apesar de que temos casos de caminhos com até 19 saltos (passando pela rede toda), a média e a mediana de saltos, para este exemplo, estão em torno de 9 saltos. Nós vimos também que em média 8,0% dos caminhos aleatórios encontrados (desvio padrão de 1,7%) são caminhos pequenos (tamanho menor 3). Isso nos mostra que, apesar de ser uma técnica simples, apenas navegando de forma aleatória é possível encontrar caminhos curtos e em alguns casos até mesmo o menor caminho.

O processo max-degree é semelhante ao aleatório, com a diferença de que escolhemos o nó de maior grau a cada vez que possamos escolher. Caso os caminhos por este nó de maior grau não levem ao nó destino, retornamos e tentamos o segundo nó de maior grau e assim sucessivamente. Observe que esta é uma estratégia completamente determinística e o seu resultado depende fortemente da posição dos nós origem e destino em relação aos nós de maior grau. 

Considerando o exemplo acima (origem em 16 e destino em 17), o caminho encontrado tem tamanho 4 e contém os nós 16, 15, 1, 11 e  17, nesta ordem. Observe como nesse caminho, a cada passo, o nó de maior grau é escolhido.

Para entender melhor como o processo max-degree se comporta façamos o seguinte experimento. Para cada par de nós da rede em estudo, vamos calcular o caminho usando o processo max-degree e o menor caminho (mincam) usando os algoritmos tradicionais. Em seguida calculamos quantas vezes max-degree é maior do que mincam. Então um valor de 1, significa que são iguais e um valor de 5 significa que max-degree é 5 vezes maior do que mincam (se mincam é de 2 saltos, então max-degree tem 8 saltos).

O histograma abaixo mostra o resultado deste experimento. Embora o processo max-degree possa encontrar caminhos muito longos, com mais de 15 vezes o tamanho do menor caminho, observamos que tipicamente os caminhos não são tão longos quanto estes. Podemos observar que a maior parte (75%) dos caminhos encontrados por max-degree são até 7 vezes maiores do que os menores caminhos. Além disso, 50% dos caminhos encontrados por max-degree são até 5 vezes maiores do que o menor caminho.

É surpreendente como mecanismos tão simples, podem ser eficazes na busca de informação em uma rede complexa, não é? Tais processos emulam, por exemplo, o que ocorre ocorre na Web. A busca em profundidade guarda memória por onde passamos e isso é similar ao processo em que navegamos de uma página e retornamos à página anterior, caso a nova página não contenha o que buscamos e nem tenha links promissores. 

O processo aleatório indica os casos de busca em que não temos muito contexto para a escolha da próximo página, enquanto que o max-degree mostra os casos em que usamos indícios da popularidade da página como guia em nossa consulta.

Como deve ter ficado claro, tanto a escolha dos nós origem e destino quanto a topologia da rede têm influencia sobre este mecanismo de busca. Vimos aqui o comportamento do processo em uma rede G(n,m), mas como será que se comportam estes processos em redes GWS e GBA? Responderemos esta pergunta em um próximo artigo.