Modelo de Watts e Strogatz

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde fevereiro de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)


Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde fevereiro de 2014).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.



O modelo de Watts-Strogatz é um modelo aleatório de geração de grafos que produz grafos com propriedades de pequeno mundo, incluindo comprimentos de trajeto médios curtos e alta clustering. Foi proposto por Duncan J. Watts e Steven Strogatz no seu artigo da Nature Joint 1998. O modelo também ficou conhecido como o (Watts) modelo beta depois Watts usado β para formulá-la no seu livro de ciência popular Six Degrees.


Justificativa para o modelo[editar | editar código-fonte]

O estudo formal de grafos aleatórios remonta ao trabalho de Paul Erdös e Alfred Rényi. Os grafos que eles consideraram, agora conhecidos como grafos clássicos ou Erdös-Rényi (ER), oferecem um modelo simples e poderoso, com muitas aplicações.

No entanto, os grafos de ER não têm duas propriedades importantes observadas em muitas redes do mundo real:

  1. Eles não geram aglomeração local e encerramentos triádicos. Em vez disso, porque eles têm uma probabilidade constante, aleatória, e independente de dois nós serem ligados, grafos ER têm um coeficiente de clustering baixo.
  2. Eles não contam para a formação de hubs. Formalmente, a distribuição grau de grafos ER converge para uma distribuição de Poisson, em vez de uma lei de potência observada muitas vezes no mundo real, em redes scale-free.

O modelo de Watts e Strogatz foi concebido como o modelo mais simples e possível que elimina a primeira das duas limitações. É responsável pelo agrupamento, mantendo os comprimentos médios de caminho curto do modelo ER. Fá-lo por interpolação entre um grafo de ER e uma rede de anel regular. Consequentemente, o modelo é capaz de explicar, pelo menos em parte, os fenómenos de "pequeno mundo", numa variedade de redes, como a rede elétrica, a rede neural de C. elegans e uma rede de atores do filme.


Algoritmo[editar | editar código-fonte]

Dado o número desejado de N nós, o grau médio K (assumido como sendo um inteiro par) e um especial de parâmetro β, satisfazendo 0 ≤ β ≤ 1 e N ≫ K ≫ ln(N) ≫ 1, o modelo constrói um grafo não direcionado com N nós e \frac{NK}{2} arestas da seguinte forma:

  1. Construir uma estrutura de anel comum, um grafo com N nós cada um ligado a K vizinhos, K/2 em cada lado. Isto é, se os nós são rotulados n_0 \ldots n_{N-1}, existe uma aresta (n_i, n_j) se e só se  0 < |i - j|\mod {(}N-1-{\frac{K}{2}}{)} \leq \frac{K}{2}.
  2. Para cada nó n_i=n_0,\dots, n_{N-1} ter cada aresta (n_i, n_j) com i < j, e voltar a ligar com probabilidade β. A religação é feito através da substituição (n_i, n_j) com (n_i, n_k) onde k é escolhido com probabilidade uniforme de todos os valores possíveis que evitem a laços independentes (k ≠i) e hiperligar a duplicação (não há aresta ((n_i, n_{k'}) com k' = k neste momento no algoritmo).


Propriedades[editar | editar código-fonte]

Watts–Strogatz graph

A estrutura de rede subjacente do modelo produz uma rede de cluster no local, e os links aleatórios reduzem drasticamente os comprimentos médios de caminho. O algoritmo apresenta-se sobre \beta\frac{NK}{2} arestas não treliçadas. Variando β torna possível interpolar entre uma rede regular (β = 0) e um grafo aleatório (β = 1) aproximando-se do grafo aleatório Erdös-Rényi G(n, p) com n=N e p = \frac{NK}{2{N \choose 2}}.

As três propriedades de interesse são o caminho médio, o coeficiente de clustering, e a distribuição de grau.


Duração média do caminho[editar | editar código-fonte]

Para um anel de treliça a duração média de caminho é l(0)=N/2K\gg 1 e escala linearmente com o tamanho do sistema. No caso limite de β →1 o grafo converge para um grafo aleatório clássico com l(1)=\frac{\ln{N}}{\ln{K}}. No entanto, na região intermédia 0 < β <1 o comprimento do caminho médio cai muito rapidamente com o aumento β, aproximando-se rapidamente do seu valor limite.


Coeficiente Clustering[editar | editar código-fonte]

Para o anel treliça o coeficiente de clustering C(0)=\frac{3(K-2)}{4(K-1)}, e assim tende a 3/4, de forma que K cresce, independentemente do tamanho do sistema. No caso limite de β→1 o coeficiente de clustering atinge o valor para grafos aleatórios clássicos, C(1)=K/N e é assim inversamente proporcional ao tamanho do sistema. Na região intermediária do coeficiente de clustering continua muito perto do seu valor para a rede regular, e só desce relativamente ao β alto. Isso resulta numa região onde o caminho médio desce rapidamente, mas o coeficiente de clustering não, explica-se o fenómeno de "pequeno mundo".

Se utilizar a medida Barrat e Weigt para o clustering C'(\beta) definida como a fracção entre a média do número de arestas entre os vizinhos de um nó e o número médio de possíveis arestas entre estes vizinhos ou, alternativamente,

C'(\beta)\equiv\frac{3\times \mbox{number of triangles}}{\mbox{number of connected triples}}
então temos  C'(\beta)\sim C(0)\left(1-\beta\right)^3.


Distribuição grau[editar | editar código-fonte]

O grau de distribuição, no caso da estrutura de anel é apenas uma função delta de Dirac centrada em K. No caso limite de β→1 é a distribuição de Poisson, como com os grafos clássicos. A distribuição grau para 0 < β < 1 pode ser escrita como:

P(k) = \sum_{n=0}^{f\left(k,K\right)} C^n_{K/2} \left(1-\beta\right)^{n} \beta^{K/2-n} \frac{(\beta K/2)^{k-K/2-n}}{\left(k-K/2-n\right)!} e^{-\beta K/2}

onde k_i é o número de arestas que o nó possui i^{th} ou a sua gravidade. Aqui k\geq K/2, e f(k,K)=\min(k-K/2,K/2). A forma do grau de distribuição é semelhante à de um grafo aleatório e tem um pico pronunciado em k=K e decai exponencialmente para |k-K|. A topologia da rede é relativamente homogénea, e todos os nós têm mais ou menos o mesmo grau.


Limitações[editar | editar código-fonte]

A principal limitação do modelo é que ele produz uma distribuição de grau irrealista. Em contraste, as redes reais são muitas das vezes redes scale-free heterogéneas em grau, com “hubs” e um grau de distribuição de scale-free. Essas redes são melhor descritas quando o respeito pela família de modelos de fixação preferencial, como o modelo Barabási-Albert (BA). (Por outro lado, o modelo de Barabási-Albert não consegue produzir os altos níveis de clustering visto em redes reais, uma lacuna não compartilhada pelo modelo de Watts e Strogatz. Assim, nem o modelo de Watts e Strogatz nem o modelo Barabási-Albert deveriam ser considerados como totalmente realista.)

O modelo de Watts e Strogatz também implica um número fixo de nós e, portanto, não pode ser utilizado para moldar o crescimento da rede.