O fenómeno dos pequenos mundos


 Estatistica Matematica Mundo Pequeno Intercacao Social Rede Social Networking "A cena é familiar. Suponha o leitor que está numa festa com dezenas de pessoas. Naturalmente, conhece algumas delas e não conhece outras. De repente, dá-se conta de que dois seus conhecidos que julgava nada terem que ver um com o outro — digamos, um dos administradores da sua instituição e um antigo colega de liceu que já não via há 15 anos — se conhecem mutuamente. Ou que, ao conversar com alguém que acabou de lhe ser apresentado, descobre que esse alguém afinal é cunhado de um dos melhores amigos daquele seu colega que vive numa cidade distante. Dificilmente conseguirá escapar ao lugar-comum que todos repetimos em circunstâncias semelhantes: «O mundo é pequeno!»"

Este fenómeno, está na base dos recentes serviços de internet que se baseiam na criação de uma rede de pessoas que estão ligadas entre sí, por outras palavras, uma rede social ou social networking. Independentemente da tendência e dos serviços que nascem com este conceito, é natural ouvir falar, ou mesmo falar de social networking sem conhecer minimamente o princípio que esta por detrás do tema. Assim, deixo-vos um artigo do professor Jorge Buesco, publicado no livro "da falsificação de euros aos pequenos mundos", que aflora muito bem este problema matemático que esteve na base da criação de serviços como o Orkut, Hi5, flickr e muitos outros.

da falsificação de euros aos pequenos mundos O mundo é pequeno Jorge Buescu

Curiosamente, resultados recentes de investigação matemática vieram mostrar que este lugar-comum é muito mais profundo do que parece. Num certo sentido muito preciso, as teias de relações humanas estão quase fatalmente — e surpreendentemente — condenadas a evidenciar um fenómeno deste tipo, conhecido na literatura científica precisamente como fenómeno dos «pequenos mundos» e no imaginário popular como os «seis graus de separação». Esta ideia consiste no «facto» de qualquer ser humano — o leitor, por exemplo — estar apenas a seis pessoas de distância de qualquer outra — o Papa ou Nelson Mandela ou um anó nimo cidadão japonês — no sentido em que o leitor conhece alguém que conhece alguém que... até chegar ao Papa (ou Mandela ou ao dito cidadão japonês) no máximo em seis passos.

A história começa no final dos anos 60, com uma famosa experiência do psicólogo norte-americano Stanley Milgram (célebre pelas suas experiências muito polémicas sobre os efeitos da autoridade no comportamento humano). Milgram enviou um conjunto de pacotes a cidadãos do Nebraska e Kansas, com instruções para os destinatários os reenviarem a conhecidos seus com o objectivo final de os fazer chegar a uma dada pessoa no Massa­chusetts, com a qual não tinham qualquer relação. Os seus resultados foram surpreendentes: os pacotes atravessaram os Estados Unidos e chegaram ao destino através destas cadeias, em média, ao fim de cinco passos! Realizando correcções estatísticas (houve pacotes que nunca chegaram ao destino), a conclusão de Milgram foi que o comprimento médio de uma cadeia de conhecimentos que leva de uma pessoa a qualquer outra é seis. Ou seja, qualquer pessoa está separada de outra qualquer por seis apertos de mão — «seis graus de separação». É claro que este estudo empírico em si não prova grande coisa. No entanto, esta ideia perturbadora enraizou-se na cultura popular. É esta a origem da expressão «seis graus de separação» que dá nome à peça de teatro de 1990 do dramaturgo americano John Guare e ao filme de 1993 de Fred Schepisi: uma das personagens; Ouisa, afirma a certa altura que «[...] todas as pessoas neste planeta estão separadas entre si por apenas seis outras pessoas. Seis graus de separação. Entre nós e qualquer outra pessoa do planeta. O Presidente dos Estados Unidos. Um gondoleiro de Veneza. Um esquimó [...] estou ligado a qualquer pessoa do planeta por uma cadeia de apenas seis pessoas. É uma ideia profunda... cada pessoa é uma porta que se abre para novos mundos.»

Por outro lado, a ideia deu origem a variantes curiosas como, por exemplo, o jogo Six Degrees of Kevin Bacon, implementado na Internet pelo Departamento de Ciência de Computação da Universidade da Virgínia através de um programa chamado O Orá -culo de Bacon. Dê-se a cada actor que contracenou com Bacon nalgum filme o «número de Bacon» 1, a um actor que nunca con -tracenou com Bacon mas que contracenou com alguém que contracenou com Bacon o número 2, etc. O número de Bacon mede assim a «distância cinematográfica» de um qualquer actor a Bacon. Existem actores completamente separados de Bacon? A resposta é não: o número de Bacon máximo é 6. Mais: o número de Bacon «médio», num universo de quase 300 000 acto res, é surpreendentemente baixo: cerca de 2,9. Por exemplo, Maria de Medeiros tem número de Bacon 2: entrou em Pulp Fiction contra cenando com Amanda Plummer, que por sua vez contrace nou com Bacon em Elizabeth Jane. Joaquim de Almeida tem número de Bacon 3, ligando-se a ele através de Aurore Clement e Vittorio Gassman. O Mundo de Hollywood é muito, muito pequeno. Se o leitor tiver curiosidade em calcular o número de Bacon do seu actor preferido (bem como a lista de ligações cine matográficas que a ele conduzem) é convidado a visitar O Oráculo de Bacon em http://www.cs.virginia.edu/oracle/).

Um exemplo particularmente caro aos matemáticos é o do «número de Erdös». Paul Erdös, matemático húngaro falecido em 1996, foi a par com Euler o matemático mais produtivo de todos os tempos. Publicou mais de 1500 artigos, muitos deles em colaboração. Os matemáticos tiveram então a ideia de cal cular o «número de Erdös»: se um matemático publicou um artigo em colaboração com Erdös, o seu número é 1; se não publicou mas publicou um artigo conjunto com alguém que o fez, o seu número é 2, etc. Há 507 matemáticos com número de Erdös 1 e mais de seis mil com número de Erdös 2. O autor destas linhas, por exemplo, tem número de Erdös 4. Também a matemática é um pequeno mundo. Curiosamente, o próprio Erdös tem o número de Bacon 4: ele entrou em filmes sobre Mate mática! Tudo isto parecem ideias mais ou menos vagas e folclóricas. Curiosidades engraçadas para referir num animado jantar com amigos, mas com pouca ou nenhuma substância científica. E assim permaneceram as coisas até 1998 e à publicação na Nature de um artigo dos matemáticos Duncan Watts e Steven Strogatz, da Universidade de Cornell, intitulado «Dinâmica colectiva de reticulados de ‘pequenos mundos’». Duncan Watts forneceu entre­tanto uma versão mais profunda e pormenorizada do seu trabalho numa sucessão de artigos, culminando no seu livro Small Worlds, publicado pela Princeton University Press em 2000. O trabalho de Watts e Strogatz é curioso, porque não se pode catalogar em nenhum ramo fixo da Matemática. Pelo contrário, ele vai buscar ideias e métodos a ramos diferentes; alguns resulta dos são teoremas formais, outros são obtidos através de simulação por computador. O conjunto, no entanto, é extremamente interessante e abre as portas a um novo campo de investigação de enorme importância científica e tecnológica.

Como é possível abordar matematicamente o fenómeno dos pequenos mundos, em que dada uma teia de relações (seja de conhecimento social, de contracenar em filmes ou de escrever em conjunto) se pretende descobrir o caminho com menos ligações que vai de um ponto para outro? A resposta está no conceito de grafo, introduzido pelo matemático suíço Leonhard Euler no século xviii. Suponhamos que temos um conjunto finito — por exemplo, um conjunto de pessoas — em que cada elemento pode ou não estar relacionado com os outros através de uma relação — por exemplo, o conhecimento pessoal. Uma forma muito útil de repre sentar simultaneamente o conjunto de todos os elementos e de todas as relações é representando os elementos do conjunto através de pontos — chamados de vértices do grafo —, unindo dois vértices distintos por meio de uma linha — chamada aresta do grafo — no caso de eles estarem relacionados. Por exemplo, pode mos ver na figura 1 o grafo da relação de conhecimento mútuo correspondente a um conjunto de quatro pessoas que se conhecem todas entre si. A ordem de um vértice é o número de arestas que emanam desse vértice. Por exemplo, no grafo acima todos os vértices têm ordem 3: de todos os vértices emanam exactamente três arestas. Isto é apenas uma forma diferente de dizer que cada pessoa conhece outras três.

A teoria de grafos é o estudo sistemático das propriedades de grafos; permite retirar conclusões por vezes surpreendentes. ­Suponhamos, por exemplo, que a este grupo (chamado clique, porque todos se conhecem entre si) se junta uma quinta pessoa, que apenas conhece duas delas. O grafo correspondente será o da figura 2. Um problema que certamente todos ouvimos na infância é o de tentar desenhar estes grafos com um só traço, sem levantar a caneta do papel, e percorrendo uma só vez cada aresta. No segundo caso isso é possível, no primeiro impossível. A razão entende-se facilmente. Para percorrer uma só vez cada aresta só há duas hipóteses: ou todos os vértices têm ordem par (tem de ser possível chegar e voltar a partir do mesmo vértice), ou todos os vértices menos dois (o ponto de partida e de chagada, se forem diferentes) têm ordem par. Ora no segundo caso há dois vértices com ordem 3, dois com ordem 4 e um com ordem 2. O percurso é possível, desde que comece e termine nos vértices de ordem ímpar. Já no primeiro caso todos os quatro vértices têm ordem 3 e, portanto, o problema é impossível. Este é um problema que, embora de solução elementar, mostra qual o tipo de questões que se podem colocar em teoria de grafos.

De forma análoga, podemos construir o grafo da «colaboração matemática», em que a relação entre vértices (os matemáticos) é ter publicado um artigo em co-autoria, ou o grafo «de Bacon», em que a relação entre vértices (os actores) é terem contracenado num filme, etc. A análise de grafos é precisamente o elemento matemático de base considerado por Watts e Strogatz. Por aqui começa logo a ver-se que o problema dos «seis graus de separação» não é trivial. Pensemos no grafo das relações de conhecimento entre pessoas. Uma abordagem ingénua poderia colocar a questão da seguinte forma: cada pessoa no mundo conhece, digamos, cem outras. Assim, ao fim de seis iterações, o número de conhecimentos cresceu exponencialmente para 1012, o que é mais de cem vezes superior à população mundial. Não é, pois, de espantar que existam apenas seis graus de separação! A falácia, evidentemente, está em que as relações de amizade não são independentes. É impossível que todos os amigos de um amigo meu me sejam desconhecidos! Matematicamente, o «grafo das relações sociais» não tem uma estrutura em árvore: pelo contrário, as arestas entrecruzam-se e sobrepõem-se. É um grafo extremamente complicado, cuja estrutura exacta é impossível de determinar (e, além disso, varia com o tempo). Assim, quaisquer resultados matemáticos sobre este problema têm de ser resultados sobre classes de grafos.

A abordagem de Watts e Strogatz foi a seguinte. Consideremos um conjunto com n elementos em que cada elemento se relaciona com k outros elementos. Que tipos de grafos podem surgir? Num extremo estão os grafos regulares, de tipo cristalino: cada elemento relaciona-se apenas com os k vizinhos mais próximos. Do ponto de vista social isto representa um extremo abso lutamente paroquiano: cada pessoa conhece apenas as que vivem nas casas mais próximas — e mais ninguém. Chamemos a este o mundo paroquiano. No outro extremo, surge um grafo totalmente aleatório: as k ligações de cada vértice distribuem-se de forma totalmente aleatória por entre os outros n - 1 vértices possíveis. Do ponto de vista social, corresponde a dois amigos de uma mesma pessoa terem uma probabilidade mínima de se conhe cerem — nomeadamente, essa probabilidade é independente de terem um amigo comum. Se n for suficientemente grande, numa festa nenhum convidado conhece mais ninguém para lá do anfitrião. Chamemos a este o mundo estilhaçado.

Watts e Strogatz definem duas grandezas básicas com as quais vão caracterizar o fenómeno dos pequenos mundos. A primeira é o comprimento característico, que corresponde à média, tomada sobre todos os pares de vértices, do comprimento do percurso de um vértice a outro. O comprimento característico é, portanto, uma medida estatística do «grau de separação» entre vértices. A segunda grandeza é o «coeficiente de agregação»: a média sobre todos os vértices da fracção de vértices que, estando relacionados com um vértice comum, estão relacionados entre si. Este coeficiente mede a probabilidade de amigos de uma mesma pessoa serem amigos entre si — ou, mais geralmente, a tendência para a formação de «cliques» ou subsociedades. Neste sentido, o mundo paroquiano e o mundo estilhaçado são extremos. Para o mundo paroquiano, o coeficiente de agrega ção é muito grande mas o comprimento característico também: para se chegar ao extremo oposto da cidade é preciso bater de porta em porta. Para o mundo estilhaçado, o comprimento caracte rístico é pequeno mas o coeficiente de agregação é mínimo, ao nível do acaso. Podemos chegar a qualquer pessoa rapidamente mas seremos provavelmente forçados a percorrer a cidade várias vezes no processo.

Um modelo realista de sociedade é evidentemente intermédio entre o paroquiano e o estilhaçado. A estratégia de Watts e Strogatz foi a seguinte. Partindo de um grafo paroquiano, permitem que, com probabilidade p, cada aresta de cada vértice se desfaça e reconstitua ligando o vértice original a outro escolhido ao acaso. Ou seja, cada ligação é refeita ao acaso com probabilidade p. Para p = 0, obtém-se o mundo paroquiano; para p = 1 o mundo estilhaçado. Para p entre 0 e 1 obtêm-se modelos que se esperam realistas para o nosso mundo.

As conclusões são absolutamente surpreendentes — quase cho­cantes. O comprimento característico e o coeficiente de agregação dependem de p de formas radicalmente opostas. Enquanto o comprimento característico sofre uma queda quase na vertical em função de p, o coeficiente de agregação mantém-se praticamente constante e igual a 1 até se atingirem valores relativamente elevados de p. Ou seja: basta um pequeníssimo elemento aleatório (exemplo, p = 10-5) nas relações para que o grafo correspondente represente um mundo em que simultaneamente haja um grande grau de coesão social (amigos dos nossos amigos conhecem-se entre si) mas em que simultaneamente «o mundo seja pequeno». Mais ainda: esta situação é robusta, persistindo por mais de quatro ordens de grandeza em p, e englobando todo o intervalo de valores «realista» para p.

Watts e Strogatz chamam a este fenómeno o estabelecimento de um «pequeno mundo». Veja-se a figura 3. Este tipo de resultados tem implicações extraordinárias. O facto de um mundo ser pequeno não é determinável a partir de características locais (coeficiente de agregação). Isto é, uma pessoa não pode saber se vive ou não num mundo pequeno analisando apenas o que se passa à sua volta. Um mundo pode ser pequeno mesmo quando existem cliques indistinguíveis localmente das de um mundo «grande»!

Por outro lado, o facto de bastar em média apenas uma ligação aleatória em, digamos, 104 para transformar um mundo paro quiano em pequeno significa que é necessário um número muito pequeno de «atalhos» para realizar esta transição. Basta um pequeno conjunto de viajantes regulares para transformar um conjunto de paróquias num mundo pequeno. Por exemplo, Watts e Strogatz constroem um modelo simples de propagação de doenças contagiosas que dá origem a um pequeno mundo: basta um número pequeno de atalhos para a propagação ser epidémica.

Um fenómeno semelhante a este pode ter ocorrido em 1347--1348, aquando da propagação pandémica da peste negra à escala global — da Ásia à Europa Ocidental em dois anos, num mundo em que a comunicação física era muito difícil. De facto, a introdu -ção da peste na Europa foi feita por uma única pequena frota geno -vesa proveniente do porto asiático de Kaffa em 1348. À medida que ia sendo expulsa dos vários portos a que aportava, espalhava a peste. Bastou um pequeno número de viajantes para transformar um mundo de comunidades medievais isoladas num pequeno mundo, com consequências devastadoras: desapareceu entre um terço e metade da população europeia em dois anos. Este facto não pode deixar de nos preocupar, numa altura em que o mundo é mais pequeno do que nunca e o risco de terrorismo por meio de armas biológicas não é uma hipótese académica.

Outro exemplo interessante é o da conectividade da World Wide Web. Estudos recentes de L. Barabasi, em que são aplicados métodos da Física Estatística, mostram que o mundo virtual de centenas de milhão de páginas Web com links de umas para as outras é um pequeno mundo. O grau de separação entre quaisquer duas páginas Web é apenas de 19. Isto é, partindo de uma qualquer página Web podemos, em média, atingir qualquer outra no máximo com 19 clicks. Este é um bom exemplo de uma rede em evolução: estão permanentemente a ser adicionadas à Web novas páginas (vértices do grafo correspondente) e links (arestas do grafo). É interessante ainda notar que a popularidade do motor de busca Google é devida a tirar partido de a Web ser um pequeno mundo, visto que ele classifica os documentos de acordo com a posição topológica que ocupam no grafo de ligações da Web.

Outro exemplo ainda é o da evolução da linguagem. A rede das palavras utilizadas na linguagem comum pode ser pensada como um gigantesco grafo (que evolui com o tempo, visto que a linguagem é dinâmica) em que palavras relacionadas estão ligadas por vértices. O físico José Fernando Mendes, da Universidade de Aveiro, provavelmente o grande especialista português em pequenos mundos e investigador activo nesta área, mostrou recen temente num artigo nos Proceedings of the Royal Society que a rede de palavras na linguagem é quantitativamente um dos melho res exemplos de pequenos mundos. José Fernando Mendes publicou em 2003, em co-autoria, o livro Evolution of networks — from biological nets to the Internet and WWW na Oxford Univer sity Press. O leitor mais interessado é convidado a consultar a página Web de José Fernando Mendes em http://sweet.ua.pt/~f2064/. Todos estes exemplos revelam que as consequências científicas e tecnológicas do trabalho iniciado por Watts e Strogatz são difí ceis de imaginar, embora haja ainda muita matemática por fazer. Mas, como se vê, o espectro de potenciais aplicações é quase infindável. Essencialmente, todas as aplicações que dependem de redes interligadas podem beneficiar destes resultados. Alguns dos exemplos possíveis são redes de transmissão eléctrica, telecomunicações, a Internet, modelos de propagação de doenças infeccio sas ou de vírus de computador, o processamento de informação pelo cérebro humano, ou mesmo os fenómenos cooperativos da Física da Matéria Condensada.

Retrospectivamente, é espantosa a quantidade de problemas científicos sérios que podem beneficiar da investigação sobre o fenómeno dos «pequenos mundos». Ainda na sua infância, talvez ele se venha metaforicamente a revelar um «atalho» no grafo dos problemas científicos e contribua para transformar o mundo da ciência num... pequeno mundo, com poucos graus de separação.


obvious magazine

There are those that look at things the way they are, and ask why? I dream of things that never were, and ask why not?
Saiba como escrever na obvious.
version 1/s/tecnologia// @obvious, @obvioushp //obvious magazine