Redes de pequeno mundo

Rede de pequeno mundo é um tipo de grafo matemático no qual grande parte das conexões são estabelecidas entre os vértices mais próximos, apresentando-se como um mundo pequeno. Neste tipo de rede, a distância média entre quaisquer dois vértices não ultrapassa um número pequeno de vértices.
Especificamente, uma rede do tipo Pequeno Mundo é definida para ser uma rede em que a típica distância L entre os dois nodos escolhidos aleatoriamente (o número de etapas necessárias) cresce proporcionalmente ao logaritmo do número de nodos presentes na rede N (L αlog N).
Muitos destes grafos são representados através desta rede do tipo Pequeno Mundo. As redes sociais, ligações de Internet, páginas interligadas como a Wikipedia são exemplos das características deste tipo de rede. Duncan Watts e Steven Strogatz[1998] observaram e identificaram certas categorias de redes do tipo comunidade como classes de grafos aleatórios.

Classificando-os de acordo com duas características de estrutura independentes, ou seja, o coeficiente de agrupamento, e média-node para o nó-distância (também conhecido como média comprimento do caminho mais curto).

O tipo de Redes de Pequeno Mundo construídos de acordo com o modelo clássico e pioneiro de Erdős-Rényi (ER), apresentam agrupamentos locais e um diâmetro pequeno o qual representa o maior caminho geodésico entre 2 vértices. Isto é, podem ser observados “grupos de vértices” com laços mais fortes, formando assim pequenas comunidades dentro da rede sendo que a existência de agrupamento é indicada pelo valor do coeficiente de agregação.

Propriedades

O efeito Pequeno Mundo pode ser observado nas redes nas quais os vértices estão interligados através de um caminho mínimo. Este caminho mínimo, chamado de caminho geodástico ou distância geodástica, é calculado como sendo o menor número de arestas entre um vértice de origem e um de destino. O coeficiente de agregação, que é uma medida do subgrafo formado por vi e a sua vizinhança, varia significativamente em redes do tipo comunidade, sendo maior nos vértices que integram as comunidades e menor nos vértices que interligam comunidades (hubs). Isto significa que apresentam subgrafos (comunidades) com grau alto e, ao mesmo tempo, poucas arestas entre o subgrafo que está a ser considerado e o restante da rede. Em redes do tipo Pequeno Mundo a distância entre os vértices tende a crescer proporcionalmente a log10 |V| (COMELLAS, SAMPELS, 2002).

Exemplos de Redes do Tipo Pequeno Mundo

Redes do Tipo Pequeno Mundo são encontradas em muitas situações do mundo real, tais como, mapas de estradas, cadeias alimentares, redes de energia elétrica, redes de processamento de metabolismos, redes de neurônios, redes de eleitores, gráficos de chamadas telefônicas e redes de influência social.

Robustez da Rede

Watts tratava as suas redes sociais como redes aleatórias, ou seja, redes em que as conexões entre os nós (indivíduos) eram estabelecidas de modo aleatório. Entretanto, Barabási demonstrou que as redes não eram formadas assim e que a prevalência de redes de Pequenos Mundos em alguns tipos de sistemas podiam refletir uma vantagem evolutiva de cada arquitetura. Ou seja, que as redes tinham uma ordem na dinâmica de estruturação, como também de resto os estudos de Watts e Strogatz, mas que ao contrário do modelo destes autores, essa ordem não era aleatória. Dependia do grau de notoriedade ou popularidade que cada nó possuía. Esse padrão de estruturação, ficou conhecida por Barabási de “rich get richer” (Barabási, 2002).
Numa rede aleatória, na qual todos os nós têm aproximadamente o mesmo número de ligações, a exclusão de um nó aleatório faz com que aumente a probabilidade do caminho se tornar mais curto de forma significativa, para qualquer que seja o nó excluído. Neste sentido, as redes aleatórias são vulneráveis a perturbações aleatórias, enquanto redes de pequeno mundo são mais robustas.

Construção

O modelo de Watts-Strogatz usa os seguintes parâmetros:

• N -> número de nós;
• K -> grau de cada nó;
• (0 <= P <= 1) -> coeficiente que modela o grafo, quanto maior P, maior a desordem;
• C -> coeficiente de agregação;
• L -> distância média entre dois nós da rede.

Para construir uma rede de Pequeno Mundo é necessário começar com uma matriz circular de N vértices. Os n nós são organizados num círculo e as arestas são definidas entre um nó e seus k nós mais próximos. Para cada aresta, escolher uma nova extremidade com probabilidade p (introduzir aleatoriedade) e escolher de forma uniforme entre os restantes nós. Esta construção permite ajustar a topologia da rede, a partir de um valor de p = 0 (rede regular, tal como uma rede , em que cada nó está conectado regularmente com vizinhos) para completar a desordem (p = 1). As redes que cumprem o critério 0 < p <1 têm propriedades de pequeno mundo.

Aplicações para a computação

Redes de Pequeno mundo têm sido usadas para estimar a usabilidade da informação armazenada numa base de dados de grandes dimensões. A medida é denominada Medida de Transformação de dados de Pequeno Mundo.Quanto maiores forem as ligações da base de dados a uma rede de pequeno mundo mais probabilidades um utilizador vai ter em extrair a informação no futuro com sucesso.