Seis graus de separação

blog6degreesnetzwerk_thumb

Neste artigo vou-vos falar da origem do conceito de “seis graus de separação”, bem como da sua relação com o nascimento da Teoria de Redes Complexas – uma nova área da Física que estuda problemas aparentemente distintos, desde redes sociais, passando por redes tecnológicas e de informação, até redes biológicas.

Em 1909, Guglielmo Marconi ganhou o prémio Nobel da Física pelas suas contribuições na invenção do rádio (ou telegrafia sem fios, como era chamado na altura). Na cerimónia de entrega do prémio, Marconi proferiu um discurso no qual sugeriu os seis graus de separação na rede de comunicações por rádio.

O que significam estes “seis graus de separação”? Avancemos 20 anos, até ao ano de 1929, quando o escritor húngaro Frigyes Karinthy publicou a história “Cadeias” na colecção de histórias intitulada “Tudo é diferente”. Nesta história, as “cadeias” dizem respeito às ligações interpessoais de conhecidos. Tendo em conta a crescente globalização, as personagens da história inventam a hipótese de que qualquer pessoa está ligada a outra qualquer pessoa no mundo por um máximo de cinco conhecidos. Isto é, se considerarmos duas pessoas escolhidas ao acaso, digamos, o Alberto e o Isaac, então o Alberto tem um amigo, que tem um amigo, que tem um amigo, …, que conhece o Isaac. O conjunto de pessoas que “unem” o Alberto ao Isaac formam uma “cadeia” com um máximo de cinco elementos (excluindo o Alberto e o Isaac), ou seja, seis graus de separação (uma ligação de amizade constitui um grau). Embora não haja evidências (que eu conheça), é bastante provável que Karinthy tenha sido inspirado pelo discurso de Marconi (que dizia apenas respeito às comunicações por rádio).

Os-6-níveis-de-separação-do-Facebook1

Cerca de quatro décadas depois, em 1967, Stanley Milgram publica o primeiro estudo na área de psicologia social sobre o tema do “pequeno mundo” (small world). Milgram começa o seu artigo com uma história “típica” de duas pessoas que se conhecem por acaso na Tunísia e que descobrem, para seu enorme espanto, que têm um amigo em comum do outro lado do mundo. Concluem, por isso, de forma coloquial que o mundo é pequeno. Partindo deste exemplo ilustrativo, Milgram alega que este tipo de “coincidências” ocorre com maior frequência do que o que seria de esperar. A partir daqui estabelece a questão de determinar quantas pessoas terá a cadeia que liga quaisquer duas pessoas escolhidas ao acaso. Reconhece ainda que esta questão decorre de uma mais profunda: qual a estrutura matemática da sociedade? Colocando de parte esta última questão, Milgram estuda a do número de pessoas envolvidas na cadeia fazendo uma experiência simples: escolhe pessoas ao acaso nos Estados Unidos, dá-lhes uma carta, diz-lhes que o objectivo é que a carta chegue a uma dada pessoa em Boston, e que têm de enviar a carta para um conhecido seu. (Por exemplo, imaginem que Milgram deu uma carta ao John que vivia em Miami, e lhe disse que o objectivo era fazer chegar a carta ao Bob que vivia em Boston. O John não conhecia o Bob, no entanto conhecia a Mary que vivia em New York, que fica relativamente próximo de Boston, e por isso enviou para ela. Consequentemente, a Mary teve de fazer o mesmo: enviar para alguém que ela conhecia que à partida desse mais chances de fazer a carta chegar ao Bob.) Como podem estar a adivinhar: os resultados de Milgram indicaram que bastavam seis entregas em média para que a carta chegasse ao destino!

Antes de prosseguir, deixem-me sublinhar alguns “detalhes” sobre a experiência de Milgram: primeiro, as pessoas foram apenas escolhidas nos Estados Unidos, portanto os “seis graus de separação” de Milgram apenas seriam aplicáveis a este país e não ao globo; segundo, as pessoas têm apenas um conhecimento parcial da estrutura social, isto é, sabem quem são os seus conhecidos, mas não quem são os conhecidos dos seus conhecidos (e muito menos os conhecidos dos conhecidos dos conhecidos…), o que significa que o caminho que as cartas tomaram não está optimizado para encontrar o seu destino no menor número possível de envios; em terceiro, notem o “em média” em contraste com o máximo da história de Karinthy, ou seja, muitas cartas passaram por mais que cinco pessoas antes de chegarem ao destino! Acrescento ainda que, infelizmente, os resultados de Milgram não podem ser considerados científicos, pois carecem de replicabilidade. A amostra de pessoas era relativamente pequena para propósitos estatísticos (apenas 300 remetentes iniciais e um só destinatário), e, pior que isso, os 300 remetentes não foram escolhidos ao acaso como Milgram alegara (muitos deles viviam em Boston, e muitos outros tinham interesses em comum com o destinatário – havia ligações de carácter profissional). Por outro lado, muitas das cartas não chegaram ao destinatário e foram simplesmente descartadas da análise.

Os “seis graus de separação” só se tornaram realmente famosos em 1990, quando John Guare publicou uma peça de teatro intitulada especificamente “Seis graus de separação”, onde expunha a ideia de forma semelhante a Karinthy (embora tenha citado Marconi como tendo sido a sua inspiração). O sucesso da peça deu lugar a um filme em 1993, o qual cimentou a popularidade do conceito, que desde então tem voltado a aparecer noutros filmes e séries televisivas.

Voltando à ciência, a experiência de Milgram foi ressuscitada em 2001 por Duncan Watts com contornos ligeiramente diferentes: trocou a carta por um e-mail. Notem que neste caso quer o remetente quer o destinatário tinham que ter uma conta de e-mail, o que, para 2001, era uma condição algo restritiva; por outro lado, o facto de possuírem o e-mail de outra pessoa não garantia que a conhecessem pessoalmente. A amostra neste caso já foi bastante significativa: 48 mil remetentes e 19 destinatários distribuídos por 157 países. O número médio de graus encontrado foi novamente seis, mas, pela primeira vez, com autoridade científica! Desde então, outros estudos semelhantes têm sido publicados. Em 2007, Jure Leskovec e Eric Horvitz encontraram em média 6.6 graus de separação entre os utilizadores do Microsoft Messenger. Mais recentemente, estudos semelhantes foram feitos para redes sociais como o Facebook e Twitter, onde se encontraram números de grau de separação inferiores: 4.74 e 4.67, respectivamente. É fácil de explicar intuitivamente o porquê de as pessoas estarem mais “próximas” nestas redes sociais: existem indivíduos extremamente populares que ligam indirectamente milhões de indivíduos desconhecidos. Mais que isso, os indivíduos extremamente populares tendem a estar ligados a outros indivíduos extremamente populares (o chamado “rich club”, clube de ricos), o que significa que quase toda a rede pode ser alcançada através das ligações destes “ídolos”.

Disassortative_network_demonstrating_the_Rich_Club_effect

Se considerarmos que esta imagem ilustra uma pequena parcela do Facebook, os pontos representam pessoas e os traços as ligações de amizade. Como podem ver, os pontos vermelhos têm muito mais ligações que os pontos azuis e formam um género de “núcleo” que une toda a rede, ou seja, formam um “rich club”. Através deles, todos os pontos estão ligados (com um máximo de 3 graus de separação).

Qual a importância de tudo isto? 

Tudo “isto” (seis graus de separação, pequeno mundo, clube de ricos, etc.) são conceitos da Teoria de Redes Complexas (uma área da Física Estatística aliada à Teoria de Grafos, uma área da Matemática). Nesta área estudam-se questões como aquela que Milgram abordou parcialmente: qual a estrutura da sociedade? Daqui decorrem imensas questões com implicações práticas: como é que essa estrutura influencia a dinâmica da sociedade?

Notem que ao subirmos para o patamar da Matemática, as redes em causa deixam de ter que ser de carácter social. Uma rede (ou grafo) é uma abstracção que pode simbolizar muitas outras coisas. Uma rede é em geral constituída por um dado número de “nodos” (também lhe podem chamar vértices) que estão ligados entre si por “ligações” (arestas):

220px-UndirectedDegrees.svg

Representação de uma rede, em que os círculos são nodos, e os traços representam ligações entre os nodos. Os números indicam o número de ligações do nodo. Muitas vezes, quanto maior for o número de ligações de um nodo, maior é a importância desse nodo para a rede. 

Numa rede social, os nodos representam pessoas, e as ligações correspondem a algum tipo de interacção entre elas (podem ser laços familiares, ligações de amizade, colegas de trabalho, etc.). Existem muitas outras redes, onde o que varia são os protagonistas: a World Wide Web (WWW) é uma rede de páginas (sites) ligados entre si através de hiperligações (links); a Internet é uma rede de computadores com comunicação de dados entre si; a rede de caminhos de ferro ou de autocarros, ou de aviões, onde os nodos são as estações ou aeroportos, e as ligações são a existência de comboios ou voos directos; a rede de telefones ou telemóveis; etc. Até um dicionário pode ser considerado uma rede de palavras, em que a interacção entre as palavras resulta das suas definições. Na Biologia também encontramos imensas redes, como seja a rede neuronal que temos no nosso cérebro.

É importante compreender o poder da abstracção matemática: ao estudarmos as propriedades de uma dada estrutura de rede, estamos a tirar ilações para todos os exemplos reais de redes que tenham essa estrutura, independentemente do que esteja representado nessas redes.

A Teoria de Redes Complexas nasceu com um óptimo exemplo disto mesmo: em 1998, Duncan Watts e o seu orientador Steven Strogatz publicaram um artigo revolucionário onde estabeleceram a noção de redes pequeno mundo. Até 98, os estudos de redes tendiam a focar-se em dois extremos: em redes aleatórias, onde cada nodo está ligado a outro nodo de forma aleatória; ou em redes regulares (ver imagem abaixo). Watts e Strogatz decidiram estudar um caso intermédio que poderia ser construído pegando numa rede regular e trocando uma dada percentagem das ligações regulares por outras aleatórias. Este novo tipo de rede continha propriedades de ambos os extremos, nomeadamente a já mencionada pequena distância média entre nodos (típica das redes aleatórias), e um elevado coeficiente de agrupamento ou de agregação (usual em redes regulares). (O coeficiente de agrupamento mede a tendência que os nodos têm de se agrupar, formando, por exemplo, triângulos.)

393440aa.eps.2

A rede do lado esquerdo é regular, a rede do meio é pequeno mundo, e a rede do lado direito é aleatória.

Nesse mesmo artigo, os autores mostraram que a rede neuronal das minhocas Caenorhabditis elegans, a rede eléctrica dos Estados Unidos, e a rede de colaborações de actores cinematográficos tinham uma estrutura de pequeno mundo (desde então, muitos outros exemplos têm sido encontrados e estudados). A partir daqui, Watts e Strogatz estudaram a relevância deste tipo particular de estrutura e mostraram que esta beneficia a sincronização entre os seus elementos. Esta propriedade é particularmente relevante para uma rede neuronal, onde a sincronização de actividade neuronal é crucial para a transmissão de informação entre neurónios.

Assim, estudando a estrutura de redes podemos compreender de que forma é que a estrutura afecta a propagação de informação. Se por um lado é importante para compreender o funcionamento do cérebro, por outro é determinante para construirmos redes de informação (como a Internet) com as propriedades desejadas.

Uma outra questão muito estudada foca-se no papel da arquitectura da rede quando ocorrem falhas no funcionamento de alguns dos elementos ou ligações da rede. Por exemplo, numa rede de distribuição eléctrica é importante encontrar a estrutura mais robusta possível contra eventuais falhas em centrais eléctricas. Ou em vez de falhas, podemos pensar em vírus (informáticos, ou humanos). Qual a melhor forma de combater uma epidemia? Se conhecermos a estrutura da rede conseguimos entender quais as melhores estratégias de vacinação, por exemplo (visto que normalmente não é possível vacinar toda a gente).

Para concluir, não posso deixar de referir uma das aplicações milionárias da Teoria de Redes: o algoritmo de pesquisa da Google. Como antes mencionei, a WWW é uma imensa rede de páginas ligadas entre si através de hiperligações. Como encontrar uma página em especial? A Google criou o algoritmo chamado “PageRank” (classificador de páginas, em tradução livre), através do qual classifica cada página tendo em conta o número de hiperligações que esta recebe de outras páginas, bem como a classificação dessas páginas. Páginas com maior classificação são de certo modo mais importantes e por isso surgem em primeiro lugar na pesquisa. (Este foi o algoritmo inicial, o actual é mais sofisticado.)

A ciência das redes é relativamente jovem, mas tem sido extremamente prolífica. Não é difícil de antecipar que muitas outras aplicações ainda estão para vir, visto que tudo o que conhecemos constitui uma enorme rede com inúmeras sub-redes.

carl_graph_theory__d8_by_eleew-d3g20jt

“É possível atravessar as sete pontes sem ter que atravessar uma mais que uma vez?”
“Como é que eu posso responder a essa questão?! Não tenho pernas!”
“Não precisas de pernas para encontrar a resposta!”
A questão em causa é conhecida como o problema das sete pontes de Königsberg, ao qual Leonhard Euler deu resposta em 1736. A sua solução representou o nascimento da Teoria de Grafos. De facto, não é preciso “experimentar”, basta analisar matematicamente o problema para compreender que a resposta é não. Para atravessar todas as sete pontes é necessário atravessar pelo menos uma delas duas vezes.

Deixe um comentário

O seu endereço de email não será publicado.

Este site utiliza o Akismet para reduzir spam. Fica a saber como são processados os dados dos comentários.

Verified by MonsterInsights