Escola de Redes

REDES COMPLEXAS: DA INTERNET ÀS REDES SOCIAIS

A dica foi do Gabriel de Andrade. Trata-se de matéria publicada no site PRISMA À LUZ DA FÍSICA do CFTC - Centro de Física Teórica e Computacional de Portugal. Reproduzo abaixo o capítulo intitulado A Física dos Sistemas Complexos. Na verdade, apenas o tópico Redes complexas: da Internet às redes sociais. Pode servir como um bom roteiro introdutório ao nosso tema central.

SEIS GRAUS DE SEPARAÇÃO

O mundo é pequeno!


Connecto ergo sum. (Björneborn, 1998)

Todos, provavelmente, já utilizámos ou já ouvimos a frase o mundo é pequeno! Contudo foi só com os trabalhos do psicólogo Stanley Milgram, nos anos 60, que esta constatação aparentemente banal começou a ganhar o estatuto de facto experimental. Milgram enviou 160 cartas para pessoas escolhidas ao acaso em dois estados norte-americanos, pedindo-lhes que as procurassem fazer chegar a um destinatário alvo, cujo nome, profissão e zona de residência eram dados. Para isso, e caso não o conhecessem, deviam enviar a carta para algum amigo que achassem que pudesse eventualmente conhecer o destinatário. Das 160 cartas, 42 chegaram ao destino e nestas o número médio de intermediários foi... 6!

Esta experiência parece confirmar a ideia de que a distância, medida em número de ligações de conhecimento directo, ou graus de separação, entre dois elementos típicos de uma rede de ligações sociais é de facto bastante pequena, mesmo em redes com muitos elementos, como a sociedade americana dos anos sessenta.

Existem outras experiências, em áreas tão diversas como a matemática ou a comunidade cinematográfica, que dão resultados semelhantes. O jogo de Bacon, na comunidade de actores de Hollywood, consiste em atribuir a quem tenha participado num filme juntamente com este actor o número de Bacon 1, o número de Bacon 2 a quem tenha participado num filme com alguém que tenha participado num filme com Bacon, e por aí fora. O número de Bacon mede a distância a este actor no universo dos actores de Hollywood e pode não estar definido para um dado actor, se não for possível ligá-lo a Kevin Bacon por uma cadeia de actores que tenham contracenado juntos em algum filme. Da análise dos resultados deste jogo conclui-se que em geral o número de Bacon está definido e que o maior número de Bacon na comunidade cinematográfica americana é 8!

Números de Bacon de alguns actores portugueses


Entre os matemáticos existe desde há muito tempo um jogo semelhante, em que a ligação entre dois matemáticos se define pela publicação conjunta de um artigo, e onde a figura central do jogo é o prolífico matemático Paul Erdös. Os dados recolhidos a propósito deste jogo mostram que o número de Erdös, se estiver definido, é menor que 15; que 98% dos matemáticos têm este número menor que 8 e que a média dos números de Erdös é menor que 5. A figura seguinte mostra uma pequena porção dessa rede.

Pequena porção do grafo de colaboração de Erdös.


Qualquer das estruturas descritas nestes três exemplos pode ser representada por um grafo. Os grafos foram inventados por Euler em 1736 para resolver o famoso problema das pontes de Königsberg (a). A questão era saber se era possível atravessar as sete pontes do rio Pregel (b), passando sobre cada uma delas uma só vez, e regressar ao ponto de partida. A ideia de Euler consistiu em representar as quatro zonas da cidade, delimitadas pelo rio, por nodos e as pontes por arestas entre esses nodos (c). O objecto assim construído é um exemplo de um grafo. Pensando neste modelo, é evidente que um tal caminho só é possível se cada nodo estiver ligado a um número par de arestas, pois se se chega a uma zona por uma ponte, a condição de que cada ponte é percorrida uma só vez implica que se possa sair por uma outra. Dado que todos os nodos do grafo têm grau (número de arestas que saem de um nodo) ímpar, um caminho com aquelas propriedades é impossível.

a: mapa da cidade de Königsberg | b: as pontes de Königsberg | c: o respectivo grafo.

Os grafos são a forma elegante de codificar aquilo que na linguagem corrente chamamos redes. Um grafo é um conjunto de pontos, que representam objectos reais, ligados por arestas, que representam relações entre os objectos reais. Na figura seguinte podemos ver alguns exemplos adicionais do que os nodos e arestas podem representar.

Alguns exemplos de grafos


Nalguns casos faz sentido dar uma direcção à aresta que liga dois nodos, como por exemplo no caso da cadeia alimentar, onde essa direcção indica quem come quem. A esses grafos chamamos grafos orientados. O estudo dos grafos como objectos matemáticos tem uma longa história, na qual, curiosamente, o próprio Erdös jogou um papel de primeira linha. É com base nessa história que podemos hoje compreender e continuar a estudar as propriedades das redes complexas, como as redes sociais de que acabámos de ver alguns exemplos. Em particular, vamos poder perceber porque é que o mundo é pequeno...


GRAFOS ALEATÓRIOS E O EFEITO MUNDO PEQUENO

Antes de vermos o que é um grafo aleatório, façamos uma pequena digressão pelo conceito de probabilidade. Historicamente a noção de probabilidade teve a sua origem no estudo dos jogos de azar e o seu propósito era medir quão plausível, ou não, era um determinado acontecimento.

Classicamente a probabilidade é definida pelo quociente do número de casos favoráveis pelo número de casos possíveis, quando todos os casos são igualmente plausíveis. Por exemplo quando se lança uma moeda ao ar temos dois casos possíveis: ou sai cara ou sai coroa. Como ambos os casos são igualmente plausíveis a probabilidade de sair cara é 1/2 e a probabilidade de sair coroa é 1/2. A aplicação do mesmo tipo de raciocínio ao lançamento de um dado mostra que a probabilidade de sair qualquer um dos seis números é 1/6, enquanto que a probabilidade de sair um número par é 3/6 = 1/2.

Os grafos aleatórios constroem-se da seguinte forma:

1. pega-se numa colecção de nodos,
2. pega-se numa moeda viciada que tenha probabilidade p de sair cara quando lançada ao ar, para cada par de nodos lança-se a moeda ao ar, se sair cara unem-se os dois nodos com uma aresta, se sair coroa deixam-se desligados.

Um grafo aleatório pode ser imaginado como uma colecção de botões ligados por fios, onde pares de nodos (botões) estão ligados ao acaso por intermédio de arestas (fios)

Os grafos aleatórios são o modelo mais simples que permite compreender o efeito de small world, ou porque é que o mundo social é pequeno. As suas principais propriedades foram estudadas e descritas nos anos 60 por Erdös e Rényi. Num grafo aleatório não existe nenhum critério que privilegie umas ligações em relação a outras, e portanto este fica caracterizado pelo número de nodos N e pela probabilidade p de que uma ligação qualquer das N(N-1)/2 possíveis ligações entre nodos diferentes seja estabelecida. Na figura seguinte podemos ver algumas realizações de grafos aleatórios com cem nodos para diferentes probabilidades p.

Realizações de grafos aleatórios, com 100 nodos, para diferentes valores de probabilidade p

Diferentes realizações de um grafo aleatório com N e p fixos darão origem a estruturas diferentes, mas a média do número de ligações destes diferentes grafos será igual a pN(N-1)/2. Portanto, o grau médio do grafo, , ou seja, o número médio de arestas que cada nodo tem, vem dado por =p(N-1), uma vez que cada ligação 'serve' dois nodos. Para N grande a distribuição de probabilidades para os graus dos nodos é bem aproximada por uma distribuição de Poisson de valor médio como as representadas na figura seguinte para alguns valores de .

Distribuição de Poisson para diversos valores de k

Vejamos como uma rede com esta estrutura dá origem ao efeito de small world. Escolhamos ao acaso um nodo do grafo como ponto de partida. Este nodo terá em média primeiros vizinhos, cada um dos quais também com primeiros vizinhos, ou seja, o nodo inicial tem aproximadamente 2 segundos vizinhos. Seguindo o mesmo raciocínio, o nodo inicial terá cerca de n n-ésimos vizinhos, isto é, nodos a uma distância de n graus de separação. Quando tivermos L ~ N, a cadeia construída a partir do nodo inicial pode chegar a qualquer nodo da rede, e portanto o número máximo de graus de separação num grafo aleatório é da ordem de L, que é da ordem do logaritmo de N. Ou seja, 6 graus de separação é um resultado plausível numa rede aleatória com vários milhões de nodos.

O modelo dos grafos aleatórios explica no essencial o efeito de small world. Mas será que as redes sociais são bem modeladas por este tipo de grafos?


MODELO DE WATTS E STROGATZ E O EFEITO DE VIZINHANÇA

Apesar de ser fácil trabalhar matematicamente os grafos aleatórios, este modelo é totalmente irrealista em muitos casos, devido à completa ausência de estrutura local. Pensando, por exemplo, nas redes sociais, salta à vista que a probabilidade de quaisquer dois dos meus amigos se conhecerem é bastante superior à probabilidade de duas pessoas escolhidas ao acaso se conhecerem. Na terminologia dos grafos, esta propriedade mede-se a partir do coeficiente de aglomeração C, que é a probabilidade de dois primeiros vizinhos do mesmo nodo estarem conectados entre si. Num grafo aleatório os valores de C e p são iguais, pois não há ligações privilegiadas. No entanto, para muitas redes reais, C é muito maior que p, o que mostra um importante 'efeito de vizinhança'. A tabela seguinte mostra os valores do número total de nodos N, do valor médio L da distância entre dois nodos medida em número de ligações ou graus de separação e do coeficiente de aglomeração C de várias redes reais. A coluna Crand mostra o valor do coeficiente de aglomeração para uma rede aleatória com os mesmos valores de N e de L.


Rede C Crand L N
WWW 0,1078 0,00023 3,1 153127
Internet 0,18-0,3 0,001 3,7-3,76 3015-6209
Actores 0,79 0,00027 3,65 225226
Co-autores 0,43 0,00018 5,9 52909
Metabólica 0,32 0,026 2,9 282
Cadeia Alimentar 0,22 0,06 2,43 134
Neuronal 0,28 0,05 2,65 282


Como se pode ver, as redes consideradas nestes estudos têm um coeficiente de aglomeração muito superior ao das redes aleatórias, mas têm também, como estas, valores baixos de L. Para modelar muitas das redes reais precisamos então de um modelo mais sofisticado do que o dos grafos aleatórios, que reproduza o efeito de small world sem sacrificar o efeito de vizinhança.

Watts e Strogatz propuseram em 1998 um modelo extraordinariamente simples que apresenta estas características complementares. A ideia em que o modelo se baseia é também muito simples. Por um lado, redes aleatórias estão associadas a valores baixos de L e a valores baixos de C. Por outro, a maioria das redes regulares, em que todas as ligações são locais, correspondem a valores elevados tanto de L como de C. No exemplo da figura temos uma rede regular construída sobre um anel, em que cada um dos quinze nodos está ligado aos seus dois primeiros vizinhos da esquerda e da direita. Neste tipo de rede regular, L é da ordem do número de nodos N, e C vale 1/2.

Grafo regular sobre o anel com grau 4 e 15 nodos

A ideia de Watts e Strogatz foi a de construir um modelo que interpolasse entre estes dois casos extremos, à procura de um regime intermédio em que as características complementares dos dois tipos de grafos aparecessem combinadas.

Tomemos como ponto de partida uma destas redes regulares, N nodos dispostos ao longo de um anel, com ligações locais entre cada nodo e os quatro nodos mais próximos, os dois que o antecedem e os dois que lhe sucedem sobre o anel. Com probabilidade p, substituamos cada uma das ligações locais por uma ligação aleatória. Quando p=0 temos a rede regular inicial, para p=1 obtemos uma rede aleatória, e os valores intermédios de p correspondem a redes em que a estrutura local é parcialmente substituída por ligações aleatórias.

Propriedades do grafo do modelo de Watts e Strogatz para diferentes valores de p

No gráfico seguinte podemos ver como variam C e L com p:

Coeficiente de aglomeração e distância média entre nodos em função de p

Este processo simples e não coordenado produz, para valores baixos de p, uma rede onde o coeficiente de aglomeração ainda é elevado, mas que ao mesmo tempo é um mundo pequeno, porque basta um pequeno número de ligações aleatórias para reduzir drasticamente a distância média entre os nodos em relação a uma rede regular. Este é o modelo mais simples de rede complexa, e reproduz as principais características de muitas redes socias.


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.

Rede das auto-estradas interestaduais dos Estados Unidos (bem modelado por um grafo com uma distribuição de grau homogénea)

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 aproximadamente o mesmo número de arestas. O número médio (pico da distribuição de Poisson) 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.


CRESCIMENTO DE REDES E O EFEITO MATEUS

Em 1999 Barabási e Albert sugeriram um mecanismo dinâmico simples e plausível para o aparecimento de redes scale-free com nodos altamente conectados. A ideia básica do modelo é a de que as redes não são construídas de uma só vez, mas sim ao longo do tempo, e que apesar do processo de construção ter ingredientes aleatórios, obedece também a certas regras. Mais precisamente, consideraram que à medida que a rede cresce e que novos nodos são acrescentados, estes vão-se ligar preferencialmente aos nodos com maior grau. Este cenário é plausível para muitas redes grandes. Os novos sites web tendem a ligar-se a sites populares e conhecidos. Os novos elementos de um grupo tendem a gravitar para os seus elementos mais populares. Este modelo de crescimento chama-se de ligação preferencial e o princípio de favorecer as ligações a nodos com maior conectividade, de modo que os ricos ficam mais ricos, e os pobres, mais pobres, é conhecido por efeito Mateus, por alusão a uma parábola deste Evangelho.

A preferência em estabelecer ligações com os nodos mais conectados gera uma rede scale-free

Barabási e Albert fizeram crescer uma rede a partir de um pequeno conjunto inicial de nodos, juntando em cada unidade de tempo um novo nodo com m ligações, e tomando a probabilidade de ligação de um novo nodo a cada um dos nodos existentes proporcional ao grau desse nodo. O resultado é que, independentemente do parâmetro m, a rede inicial evolui para uma rede scale-free com uma distribuição de probabilidade de grau da forma P(k) ~ k^-3, ou seja, com uma distribuição de grau em lei de potência, sem uma conectividade característica, e com representantes de todos os graus, incluindo hubs de grau muito elevado. Uma rede real com esta lei de potência é a rede de citações de artigos...

A maior limitação deste modelo é produzir apenas redes em lei de potência com expoente -3, enquanto que nas redes reais se encontram para este expoente valores entre -3 e -2. No entanto, variações deste modelo de Barabási e Albert permitem obter redes com os outros valores para o expoente da distribuição de grau. Uma destas variantes introduz o conceito de 'fitness' de um nodo, um outro parâmetro, para além do grau, que intervém na probabilidade de que um nodo da rede receba uma ligação de novo nodo, e que evita que sejam tendencialmente apenas os nodos mais antigos a acabar por ter maior conectividade. Este modelo de fitness revelou também uma correspondência entre a estatística destas redes e a de um sistema físico - o gás de bosões!

[Clique aqui para ver o programa no final da página]


REDES COMPLEXAS NA NATUREZA

Sistemas compostos por muitas unidades semelhantes que interagem entre si são muito comuns, e, em geral, a rede de interacções não é nem completamente aleatória nem completamente regular. Por isso, encontramos redes complexas nos mais diversos contextos, desde as redes de comunicações e de distribuição de electricidade às redes formadas pelas palavras em estudos linguísticos de associação, a redes sociais como a rede de co-autoria de artigos científicos, a redes biológicas como a rede metabólica na célula ou a rede formada pelos neurónios no cérebro humano, e muitos outros exemplos.

Rede de neurónios do córtex cerebral. Cortesia de Fabrice Duprat

A levedura da cerveja, Saccharomyces cerevisiæ, foi a primeira célula eucariota para a qual o conjunto de todas as proteínas e das respectivas interacções físicas (formação de complexos proteicos de longa duração, transporte ou modificação de uma delas), i.e. o proteoma, foi completamente analisado. A rede complexa associada, cf. figura seguinte, cujos os nodos são as proteínas, 1870, e as ligações, as interacções entre elas, 2240, apresenta uma estrutura do tipo scale-free. Nas redes genéticas, os nodos representam os genes e as arestas as interacções físicas entre as proteínas expressas por esses genes. Neste contexto, a perspectiva das redes complexas pode ser útil para determinar a função biológica de cada gene.

Mapa das interacções entre as proteínas da Saccharomyces cerevisiæ (proteoma). O código de cores dos nodos representa os efeitos da remoção dos genes que expressam a respectiva proteína (vermelho, letal; verde, não letal; laranja, crescimento lento; amarelo, desconhecido). Cortesia de H. Jeong

Fenómenos como a propagação de epidemias à escala mundial, de vírus informáticos na internet ou de apagões na rede eléctrica têm-nos alertado para a influência da estrutura de contactos entre os membros de uma comunidade na dinâmica deste tipo de processos. Como é natural, as redes complexas jogam um papel importante no estudo da propagação de epidemias. O tipo de rede a considerar depende naturalmente da doença que se quer estudar. Por exemplo, para doenças sexualmente transmissíveis as redes scale-free parecem, de acordo com estudos recentes, ser um bom modelo.

Rede de contactos sexuais do estudo de Potterat et al. Cortesia de Mark Newman

Por outro lado na propagação de doenças em que o contágio depende apenas de contactos sociais, como por exemplo as doenças infecciosas infantis, a rede de contactos tem as características de uma rede mundo pequeno como a do modelo de Watts e Strogatz, cf. figura seguinte.

Rede de amizades numa escola secundária americana. Código de cores dos nodos: brancos a amarelo, afro-americanos a verde e a cor-de-rosa os outros. Cortesia de James Moody

Exibições: 4866

Comentar

Você precisa ser um membro de Escola de Redes para adicionar comentários!

Entrar em Escola de Redes

Comentário de Carlos Boyle em 16 outubro 2009 às 9:04
Muy bueno el sitio

© 2017   Criado por Augusto de Franco.   Ativado por

Badges  |  Relatar um incidente  |  Termos de serviço