Usando informação local para navegar em redes complexas

No artigo anterior investigamos o desempenho de métodos de busca em redes complexas que usam uma espécie de memória (busca em profundidade) para retornar a busca a um ponto anterior. Contrapomos estes métodos ao roteamento da Internet que não tem memória, mas que usa informação global em seu processo de busca. Assim, terminamos o artigo deixando uma dúvida no ar: podemos construir uma forma de navegação usando apenas informação local e nenhuma memória? Neste artigo tentaremos responder esta questão.

Vejamos o que ocorre caso os processos sejam simplificados para fazer navegações diretas, i.e., sem memória dos nós passados e, por isso, permitindo que os nós sejam visitados mais de uma vez. Como uma melhoria deste processo, adicionaremos informação local aos nós e permitiremos que cada nó saiba quem são os seus vizinhos, assim caso o nó $v_1$ receba uma mensagem cujo destino é o nó $v_2$ que é seu vizinho, o nó $ v_1$ encaminhará diretamente a mensagem para $v_2$. Isso ajuda a diminuir o tempo de envio da mensagem, sem que seja preciso grande quantidade de memória.

Teremos então, novamente, dois processos de encaminhamento: o aleatório e o preferencial de acordo com o grau. Embora os processos sejam de busca e navegação, como os que vimos anteriormente, chamaremos estes processos de encaminhamento apenas para diferenciá-los dos processos com memória.

No processo de encaminhamento aleatório, quando chegamos a um nó, verificamos se um dos vizinhos é o nó de destino, que é o caso em que encaminhamos a mensagem diretamente ao vizinho. Caso o destino não esteja entre os vizinhos, encaminhamos a mensagem para um nó escolhido aleatoriamente segundo uma distribuição uniforme. 

A diferença no processo de encaminhamento preferencial é que, se nenhum dos nós vizinhos é o destino, encaminharemos a mensagem ao vizinho aleatoriamente escolhido de acordo com a probabilidade $\frac{d_i}{\sum_{j \in V}{d_j}}$, onde $V$ é o conjunto de vizinhos do nó que está decidindo e $i \in V$. Em outras palavras, os nós de maior grau terão maior chance de ser escolhidos.

Ambos os processos de encaminhamento param somente ao encontrar o nó buscado ou ao atingir um número máximo de saltos.

Para demonstrar o comportamento destes processos de encaminhamento em redes diferentes faremos um experimento similar ao anterior, em que utilizamos as três redes de cada modelo construídas anteriormente, e realizamos um encaminhamento tendo como origem e destino cada par de nós da rede. Neste experimento medimos, primeiramente, a taxa de falha dos métodos, contada pela fração das vezes em que os processos atingiram o número máximo de saltos, que para este experimento foi configurado como o total de nós (100).

Nós também contabilizamos, novamente, a relação entre o tamanho do caminho encontrado pelo respectivo processo de encaminhamento (aleatório ou preferencial) e o menor caminho entre o par de nós. Note que fazemos este cálculo apenas para os caminhos onde o nó de destino foi alcançado. Desta forma, poderemos comparar os resultados deste experimento com os anteriores.

Ao todo, repetimos cada processo 4.950 vezes, já que o temos 100 nós em cada rede e que fazemos o caminho em apenas um sentido, ou seja, se fizemos o processo de encaminhamento entre o nó $v_1$ e nó $v_2$, não fazemos o processo de encaminhamento de $v_2$ para $v_1$. 

A taxa de falha do processo de encaminhamento aleatório nas redes G(n,m), GWS e GBA é de, respectivamente, 0,55%, 18,57% e 0,71%. Para o processo de encaminhamento preferencial temos que as taxas de falha são, respectivamente, de 0,36%, 17,86%, 0,65%. Como se pode observar, enquanto as redes G(n,m) e GBA tem taxas de falha comparáveis, as redes GWS tem uma elevada taxa de falha. Novamente, a estrutura da rede com muitos enlaces curtos e poucos longos tem impacto neste caso. 

No caso anterior, se os nós de origem e destino estivessem em grupos diferentes, o processo poderia permanecer em um grupo e visitar todos os nós do grupo, sem localizar o nó de interesse. Contudo, em algum momento, o processo de busca retornaria (por causa da memória) e passaria para outro grupo. Note que isso aumenta o tamanho do caminho, mas a memória garante que o nó será localizado. Já no processo de encaminhamento, o processo pode ficar "preso" em um grupo ao qual o nó de destino não pertence, fazendo com que se possa visitar reiteradamente os mesmos nós do grupo sem nunca sair dele. Isso ajuda a explicar a alta taxa de falhas das redes GWS.

Agora vejamos o resultado mais surpreendente. 

Os histogramas abaixo mostram a relação entre o tamanho dos caminhos encontrados pelos processos de encaminhamento e o menor caminho em cada uma das redes. Como se pode ver, de modo geral, estes processos conseguem encontrar caminhos ainda menores do que os encontrados pelos processos de busca anteriormente introduzidos.

Os valores das medianas destes dados em todos os casos é de 7 ou menos (lembre-se que 7 significa que o caminho é 7 vezes maior que o menor caminho, assim para um menor caminho de 3 saltos, o processo de encaminhamento encontrou um caminho de 21 saltos), indicando que os caminhos encontrados pelos processos de encaminhamento são muito menores do que os vistos nos processos de busca. 

Outro aspecto que deve ser destacado é que as redes GBA parecem oferecer uma estrutura mais propícia a estes processos de encaminhamento. Um quarto dos caminhos encontrados nas redes GBA são apenas 50% maiores do que os menores caminhos (se o menor caminho é 4, por exemplo, então o caminho encontrado pelo processo de encaminhamento é 6). Isso é independente do método usado (aleatório ou preferencial). O efeito é similar nas redes G(n,m) com os caminhos no primeiro quartil sendo 66,67% maiores. Já na rede GWS, para se ter uma ideia, o primeiro quartil é de 2,25 (caminhos 125% maiores).

Note que ao acrescentarmos mais informação ao processo - agora sabemos a identidade dos nós vizinhos - podemos obter um menor número de saltos em redes GBA e com alta probabilidade de sucesso. Pode-se ainda acrescentar outra informação que diga respeito à posição do nó em um espaço métrico escondido. Neste caso, temos um espaço métrico que determina a posição de cada nó e sabemos a posição do nó buscado. Assim, a cada salto, usamos a distância entre o nó buscado e cada um dos nós vizinhos. Escolhemos então o nó com a menor distância.

O espaço métrico escondido pode ser, por exemplo, a posição global em latitude e longitude do nó, ou pode ser um espaço não claramente identificado como por exemplo o espaço que usamos na navegação Web. Ao saltar de uma página Web para outra usamos uma métrica que não é inteiramente clara para determinar a próxima página. Por exemplo, geralmente usamos a descrição do link na página em que estamos para estabelecer a similaridade da página com o conteúdo que desejamos.

Esta ideia do espaço métrico escondido e da eficiência dos processos de encaminhamento em redes complexas foi explorada por Boguñá, Krioukov e Claffy no artigo Navigability of complex networks publicado em 2008. Esse artigo fica como dica de leitura para quem quiser se aprofundar sobre o tema.