Redes sem Escala

Melanie Mitchell, no livro “Complexidade”, expressa ter certeza de você pesquisar na World Wide Web e provavelmente usar o Google como seu mecanismo de pesquisa. Na época da web antes do Google, os mecanismos de pesquisa funcionavam simplesmente procurando as palavras em sua consulta de pesquisa em um índice capaz de conectar cada palavra possível em inglês a uma lista de páginas da Web com essa palavra. 

Por exemplo, se sua consulta de pesquisa foram as duas palavras “registros da Apple”, o mecanismo de pesquisa forneceria uma lista de todas as páginas da Web com essas palavras, na ordem de quantas vezes essas palavras apareceram juntas na página fornecida. 

Era provável você receber uma página da Web sobre o preço histórico das maçãs no estado de Washington ou os tempos mais rápidos registrados na Great Apple Race na Tasmânia, como obteria uma página sobre a famosa gravadora formada em 1968 pelos Beatles. Era muito frustrante naquela época vasculhar uma infinidade de páginas irrelevantes para encontrar aquela com as informações realmente procurando.

Na década de 1990, o Google mudou tudo isso com uma ideia revolucionária para apresentar os resultados de uma pesquisa na web, chamada “PageRank”. A ideia era a importância (e provável relevância) de uma página da Web é uma função de quantas outras páginas estão vinculadas a ela, ou seja, o número de “links internos”.

O algoritmo original do PageRank era uma ideia muito simples, mas produziu um mecanismo de pesquisa tremendamente aprimorado, no qual os resultados mais relevantes para uma determinada consulta geralmente estavam no topo da lista.

Se olharmos para a Web como uma rede, com nós sendo páginas da Web e links sendo hiperlinks de uma página da Web para outra, podemos ver o PageRank funcionar apenas porque essa rede tem uma estrutura particular: como nas redes sociais típicas, existem muitos páginas com baixo grau (relativamente poucos links internos) e um número muito menor de páginas de alto grau (ou seja, relativamente muitos links internos). 

Além disso, há uma grande variedade no número de links internos entre as páginas. Isso permite a classificação significar algo para realmente diferenciar entre as páginas. 

Em outras palavras, a Web tem a distribuição de graus distorcida e a estrutura de hub descritas antes. Acontece também existir um alto agrupamento, isto é, diferentes “comunidades” de páginas da Web têm muitos links mútuos entre si.

Na terminologia da ciência de rede, a Web é uma Rede Sem Escala. Esta se tornou uma das noções mais comentadas na recente pesquisa de sistemas complexos, então Melanie Mitchell se aprofunda um pouco mais, olhando mais profundamente na distribuição de diplomas da Web e o que significa não ter escala.

Distribuição de Graus da Web

Como podemos descobrir qual é a distribuição de diplomas da Web? Existem dois tipos de links da Web: links internos e links externos. 

Suponha uma página ter um link para a sua página, mas não vice-versa: o outro tem um link externo e você tem um link interno. É preciso ser específico sobre quais tipos de links são contados. 

O algoritmo original do PageRank olhou apenas para links internos e links externos ignorados. Nesta discussão, Mitchell faz o mesmo. Chama o número de links internos para uma página de grau dessa página.

Agora, qual é a distribuição em grau da Web? É difícil, senão impossível, contar todas as páginas e links internos na web. Não há uma lista completa armazenada em qualquer lugar e novos links são constantemente adicionados e os antigos excluídos. 

No entanto, vários cientistas da Web tentaram encontrar valores aproximados usando amostragem e técnicas inteligentes de rastreamento da Web. As estimativas do número total de páginas da Web variam consideravelmente; em 2008, as estimativas variavam de 100 milhões a mais de 10 bilhões, e claramente a Web ainda estava crescendo rapidamente.

Vários grupos de pesquisa diferentes descobriram: a distribuição em grau da Web pode ser descrita por uma regra muito simples: o número de páginas com um determinado grau é aproximadamente proporcional a 1 dividido pelo quadrado desse grau. 

As redes sem escala não têm escala característica. Isso é melhor explicado comparando uma distribuição sem escala com outra distribuição bem estudada, a chamada curva em sino.

Essa forma de sino é o motivo pelo qual é frequentemente chamada de Curva de Sino. Muitas coisas têm distribuições aproximadas da curva em forma de sino: altura, peso, notas em alguns exames, notas ganhas em jogos de basquete, abundância de espécies diferentes e assim por diante. Na verdade, como tantas quantidades no mundo natural têm essa distribuição, a curva do sino também é chamada de distribuição normal.

Felizmente para nós (e ainda mais para os acionistas do Google), a distribuição de graus da Web tem uma estrutura livre de escala em vez de curva em sino. 

As redes sem escala têm quatro propriedades notáveis: 

(1) um número relativamente pequeno de nós de grau muito alto (hubs); 

(2) nós com graus em uma faixa muito grande de valores diferentes (isto é, heterogeneidade de valores de graus); 

(3) auto-similaridade; 

(4) estrutura de mundo pequeno. 

Todas as redes sem escala têm a propriedade de mundo pequeno, embora nem todas as redes com a propriedade de mundo pequeno sejam livres de escala.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão /  Alterar )

Google photo

Está a comentar usando a sua conta Google Terminar Sessão /  Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão /  Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão /  Alterar )

Connecting to %s