Redes complexas: Da internet às redes sociais

Redes Scale-Free e o efeito hub

O regime mundo pequeno do modelo de Watts e Strogatz parece descrever as principais propriedades das redes reais que vimos até agora. No entanto, neste modelo a distribuição de probabilidades para os graus dos nodos é dada por uma distribuição de Poisson com um certo valor médio <k>, ou seja, tal como nas redes aleatórias, quase todos os nodos da rede têm grau <k> ou próximo de <k>. Por outro lado, em várias redes reais é fácil observar que existem nodos com conectividade muito superior à média, os chamados hubs, assim como muitos nodos com conectividade bastante inferior à media. Por exemplo, na web o site do Yahoo! é identificável como um desses hubs.

À esquerda, rede das auto-estradas interestaduais dos Estados Unidos (bem modelado por um grafo com uma distribuição de grau homogénea); à direita rede das ligações aéreas (rede scale-free), com os hubs representados a vermelho.

Em 1999 um grupo da Universidade de Notre Dame estudou a estrutura da web e constatou a existência de vários hubs. Mas o facto mais curioso revelado neste estudo foi que a distribuição de probabilidades para os graus dos nodos segue uma lei de potência! Isto significa que, ao contrário do que acontece nas redes aleatórias e nas redes mundo pequeno, o grau dos nodos não tem um valor típico, existem sim representantes de todos os graus. As redes com esta propriedade foram baptizadas com o nome de redes scale-free, precisamente por não terem uma escala característica de conectividade.

Todos os nodos têm a­proximadamente o mes­mo número de arestas. O número médio (pico da distribuição de Pois­son) dá-nos a "escala" da rede.

Não faz sentido falar de escala ou número médio de arestas. As redes scale-free têm muitos nodos com poucas arestas e alguns nodos com muitas arestas.

Nos últimos anos estudos similares ao anterior mostraram que estas redes scale-free são bastante comuns e surgem nos contextos mais variados: a internet, alguns tipos de redes sociais, a rede de ligações aéreas entre aeroportos, redes metabólicas, etc.

Uma propriedade curiosa das redes scale-free é que, do ponto de vista de manter a sua funcionalidade, são muito robustas em relação à remoção aleatória de alguns dos seus nodos ou ligações. Em contrapartida, são muito vulneráveis a 'ataques' dirigidos aos hubs. O ataque de 22 de Outubro de 2002 aos 13 principais servidores DNS, onde 9 destes foram postos fora de serviço cerca de uma hora, é um desses exemplos.

Comparação da falha acidental de nodos numa rede aleatória e numa rede scale-free, para facilidade de comparação foram removidos os mesmos nodos. Por fim o efeito de um ataque concertado aos hubs de uma rede scale-free.

Esta robustez em relação a erros aleatórios leva-nos a crer que nos sistemas biológicos este tipo estrutura possa ter sido seleccionada evolutivamente.