Redes Pequeno-Mundo - Redes Complexas

Redes Pequeno-mundo: 

Segundo Watts and Strogatz (1998), muitas redes apresentam padrões altamente concentrados, tendendo a formar pequenas quantidades de conexões em cada vértice. Assim, eles propuseram um modelo semelhante ao de Erdös e Rény, no qual grande parte das conexões são estabelecidas entre vérices mais próximos, apresentando-se como um mundo pequeno. Nesse modelo, a distância média entre quaisquer dois vértices de uma rede muito grande não ultrapassa um número pequeno de vértices. Para isso, basta que algumas conexões aleatórias entre grupos sejam estabelecidas (Buchanan, 2002). Na figura abaixo é apresentado um exemplo de rede pequeno mundo. 

 O efeito pequeno-mundo é observado nas redes em que a maioria dos vértices se conecta a outros através de um caminho mínimo. O caminho mínimo, também chamado de caminho geodésico ou distância geodésica, é aquele formado pelo menor número de arestas que conectam um vértice origem e um vértice destino. Para melhor ilustrar esse efeito, considere os indivíduos de uma sociedade qualquer. De acordo com o experimento conduzido por Stanley Milgram em 1960, se uma carta fosse entregue a um indivíduo, que não fosse o destinatário, e ele a repassasse a um outro e, assim, por diante, em aproximadamente seis passagens ela chegaria ao destinatário. Esse resultado é uma demonstração direta do efeito pequeno-mundo, em que o caminho percorrido pela carta, partindo de um indivíduo qualquer até o destinatário, é mínimo. O comprimento 7 do caminho mínimo médio CM entre pares de vértices em um grafo não direcionado é dada pela seguinte equação, onde dij é a distância geodésica do vértice i até o vértice j. 

 Essa definição apresenta problemas nas redes com mais de um componente. Um componente é representado por um único vértice ou por um conjunto de vértices e de arestas que conectam os pares de vértices. Nas redes com mais de um componente não há um caminho conectando um vértice qualquer de um componente com um outro vértice qualquer de outro componente. Em outras palavras, há um subconjunto de vértices interconectados entre si, mas sem qualquer conexão com um outro subconjunto da rede. Para evitar problemas no cálculo da distância média geodésica, são considerados apenas os pares de nós em que há um caminho entre eles. O efeito pequeno-mundo tem implicações óbvias na dinâmica de processos em redes. Por exemplo, um boato pode se espalhar muito mais rápido se, ao invés de mil passos, levarem apenas seis para chegar de um indivíduo qualquer a outro.

Felipe Macris - 137026