Rede livre de escala

O desafio

Imagine-se como o imperador de um planeta de outra galáxia.

Conseguiu visualizar? Agora, sendo um imperador de um lugar tecnologicamente avançado, você tem uma tarefa pela frente: implantar uma rede de rotas de voo de naves espaciais no espaço aéreo de seu planeta.

Aqui está uma representação das cidades do seu planeta que o Departamento de Defesa Aérea (DDA) disponibilizou:

Para simplificar, vamos assumir que todas as rotas serão bidirecionais, ou seja, se existe uma rota de A para B, então naves podem trafegar tanto de A para B quando de B para A.

Parece difícil? Não sabe por onde começar? Não se preocupe, você não está sozinho. Para te ajudar, apresento-lhe seu conselheiro:

Seu conselheiro é muito sábio, leia o que ele tem a dizer sobre como realizar a implantação das rotas:

“Caro imperador, 

Precisamos interligar nossas 42 cidades da melhor forma possível. Uma cidade não pode ter muitas rotas, ou ela será sobrecarregada causando grande congestionamento. Para otimizar o tráfego aéreo, podemos colocar em torno de 5 rotas em cada cidade saindo para outras cidades próximas, assim será fácil ir de um ponto a outro e evitamos caos aéreo.”

Primeira solução

Se você seguir as orientações de seu conselheiro, você pode construir uma rede parecida com esta:

O que você construiu foi uma rede aleatória. Numa rede aleatória, a probabilidade de um nó (cidade) estar ligado a outros k nós (rotas aéreas) obedece a uma distribuição de Poisson.

Isto quer dizer que em geral as cidades terão de 4 a 6 conexões, e serão raros os casos que se afastam muito da média.


Novo modelo

Acontece que a solução proposta foge da realidade. Não pelo fato de estarmos tratando de extraterrestres, mas sim porque o mais comum de acontecer é que 1) não conhecemos a priori todas as cidades e 2) elas tem diferentes graus de importância.

Seu planeta começa com poucas cidades, e, ao longo do tempo, novas cidades surgem e com elas a necessidade de criar novas rotas aéreas. Estas novas rotas conectarão as novas cidades preferencialmente àquelas mais importantes do seu planeta.

Neste novo cenário, vamos fazer uma breve simulação do surgimento de novas cidades e rotas. Para economizar recursos, seu conselheiro diz-lhe para construir apenas 1 rota para cada nova cidade, e que esta rota conecte a nova cidade a uma cidade importante.

Tempo 0: mapa das 6 cidades inicialmente existentes no planeta, segundo o DDA. Os círculos na cor cinza representam cidades ainda inexistentes.

Tempo 1: primeira implantação de rede de rotas aéreas conectando todas as cidades entre si.

Tempo 2: surgem novas cidades, e seguindo a sugestão do conselheiro são criadas novas rotas, uma para cada nova cidade.

Tempo 3: o surgimento de mais cidades marca o aparecimento de hubs, cidades com um grande número de rotas.

Tempo 4: novas cidades conectam-se preferencialmente a cidades-hub.

Tempo 5: as cidades com grande número de rotas tendem a agregar cada vez mais novas rotas.

Tempo 6: todas as cidades estão conectadas, sendo possível ir de uma cidade para qualquer outra passando por poucas rotas.

Chegamos a uma rede diferente da rede aleatória. Note que esta nova rede tem 47 rotas, contra 104 da primeira. Apesar de possuir um número muito menor de rotas, as cidades estão altamente interligadas.

Para ir de qualquer cidade para qualquer outra, precisamos usar no máximo 3 rotas. Na rede aleatória era preciso até 7 rotas para ir de uma cidade a outra.

Parece que temos uma estrutura interessante em mãos. Temos uma rede livre de escala. Nestas redes a probabilidade de um nó (cidade) ter k ligações (rotas) decai quando k aumenta, segundo uma Lei de Potência.

P(k) ~ k^-γ

Fatos interessantes

Redes não servem apenas para modelar rotas aéreas alienígenas. Elas estão presentes no nosso cérebro, células, sociedade, cadeia alimentar, ecossistemas, Internet, transmissão de energia, linguagens, etc.
Apesar da importância das redes, pouco entendemos hoje de suas estruturas e propriedades.

Redes livres de escala são dominadas por um número relativamente pequeno de nós (os hubs) que estão conectados a muitos outros. Estas redes são resistentes a falhas acidentais / aleatórias, porém extremamente vulneráveis a ataques coordenados.

Caso caiam tempestades aleatórias no planeta, é pouco provável que uma das cidades atingidas seja um hub. Sendo assim, o estrago causado, o número de rotas interrompidas, é pequeno.

Por outro lado, se inimigos de outro planeta tiverem acesso aos servidores do DDA e descobrirem quais são as cidades-hub, bastaria um pequeno ataque que bloqueasse algumas destas cidades para criar um enorme prejuízo.

Slides

Este post é inspirado na leitura de um artigo de divulgação científica de Barabási e Bonabeau entitulado "Scale-free Networks",  divulgado na revista Cientific American em maio de 2003.

Farei uma breve apresentação sobre o tema amanhã, em uma aula na UFRJ. Os slides sobre Redes Livres de Escala já estão disponíveis.

[Update 22/08/2011] A apresentação foi hoje. Fiz upload da apresentação atualizada. Confira aqui os slides sobre Redes Livres de Escala atualizados:

Redes livres de escala

View more presentations from rhcarvalho

Imagens

• Alienígenas: halloweencostumes.net
• Célula: unm.edu/~mpachman
• Inception: sensesofcinema.com
• Nave espacial: adultswimuk.wordpress.com
• Poisson e Lei de Potência: wikipedia.org
• Vacina: flickr.com/mccord
• Redes: autoria própria