# Modelo de Watts e Strogatz

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 alto clustering. Foi proposto por Duncan J. Watts e Steven Strogatz no seu artigo da Nature em 1998. O modelo também ficou conhecido como modelo beta depois de Watts usar β para formulá-lo no seu famoso livro científico: "Six Degrees: The Science of a Connected Age".

## Justificativa para o modelo

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:
* 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.
* 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

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:
* 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}}$.
* 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

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

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

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

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_{K/2}^{n}\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

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.