Caminhos na rede

Um caminho é uma sequência de nós conectados em um grafo e seu tamanho é igual ao número de enlaces entre os nós inicial (também chamado origem) e final (destino). Esta medida é dada em saltos, que é o número de arestas cruzadas no caminho.

Quando há mais de um caminho possível entre dois nós, o de menor tamanho é chamado menor caminho, ou distância geodésica, ou ainda caminho direto. Se não há caminho entre quaisquer dois nós (no caso, um grafo desconexo) então assumimos que o tamanho do caminho entre aqueles nós é infinito.

Note que em um grafo pode haver mais de um menor caminho. Abaixo apresentamos um grafo e destacamos o menor caminho entre os nós 0 e 4.

Caminho entre os nós 0 e 4

Encontrar caminhos na rede é uma das tarefas mais importantes da Internet, afinal de contas, para que  meu texto chegue até você, ele é picotado em pacotes que passam por múltiplos roteadores autônomos. Isso significa que estes roteadores encontram as melhores rotas sem intervenção humana, apenas "conversando" entre si e executando algoritmos específicos para isso. Interessante, não? Podemos falar mais sobre isso em outro momento.

Um dado interessante quando lidamos com redes complexas, é que os caminhos entre os nós da rede tendem a ser menores do que esperamos. Por exemplo, qual o tamanho típico dos caminhos em uma rede com um milhão de nós e dois milhões de arestas? Incrivelmente, tipicamente os caminhos tendem a ser bem curtos com algo em torno de 10 saltos!

Note que estamos falando de valores típicos, isto é, da média, podendo haver caminhos muito mais longos do que isso e outros muito mais curtos. A métrica que usamos para capturar esta propriedade das redes complexas é o tamanho médio dos caminhos (TMC). Este valor é obtido através da média dos menores caminhos considerando todo par de nós no grafo. 

Observe que o cálculo desta métrica é bastante custoso, já que existem muitos pares de nós em uma rede complexa grande ($n(n-1)$ pares para ser exato), portanto, não se assuste se seu computador demorar demais para entregar-lhe esta conta. O fato é que com os algoritmos e computadores que temos hoje este cálculo acaba sendo relativamente rápido para redes da ordem de centenas de milhares de nós, e se usarmos estratégias para distribuir esta computação podemos calcular esta métrica para grafos ainda maiores.

Vale ainda introduzir mais alguns conceitos associados aos caminhos. Designamos a excentricidade de um nó (Ted Lewis chama de raio do nó) como o tamanho do maior dos menores caminhos possíveis deste nó para todos os outros nós do grafo. Na mesma linha, definimos o diâmetro do grafo como o tamanho da maior excentricidade do grafo. No grafo acima, temos que a excentricidade (raio) do nó $0$ é $2$ e o diâmetro do grafo é $3$ (que é a maior excentricidade, encontrada nos nós $7$ e $9$)."

Por fim, um caminho que começa e termina no mesmo nó é chamado circuito. Assim, na rede acima, se acrescentarmos os enlaces (4,9), (9,1) e (1,0) ao caminho em vermelho, teremos criado um circuito para o nó 0. Existem vários problemas clássicos na área de grafos que usam circuitos como o Circuito Hamiltoniano e o Circuito Euleriano, mas em redes complexas estes problemas não aparecem com tanta frequência.