Modelo de Watts e Strogatz

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas
v d e

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^[1]. 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:

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

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 ${\displaystyle {\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 ${\displaystyle n_{0}\ldots n_{N-1}}$, existe uma aresta ${\displaystyle (n_{i},n_{j})}$ se e só se ${\displaystyle 0<|i-j|\mod {(}N-1-{\frac {K}{2}}{)}\leq {\frac {K}{2}}}$.
2. Para cada nó ${\displaystyle n_{i}=n_{0},\dots ,n_{N-1}}$ ter cada aresta ${\displaystyle (n_{i},n_{j})}$ com i < j, e voltar a ligar com probabilidade β. A religação é feito através da substituição ${\displaystyle (n_{i},n_{j})}$ com ${\displaystyle (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 (${\displaystyle (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 ${\displaystyle \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 ${\displaystyle G(n,p)}$ com n=N e ${\displaystyle 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 é ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle C(0)={\frac {3(K-2)}{4(K-1)}}}$, e assim tende a ${\displaystyle 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, ${\displaystyle 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 ${\displaystyle 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,

${\displaystyle C'(\beta )\equiv {\frac {3\times {\mbox{number of triangles}}}{\mbox{number of connected triples}}}}$

então temos ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle k_{i}}$ é o número de arestas que o nó possui ${\displaystyle i^{th}}$ ou a sua gravidade. Aqui ${\displaystyle k\geq K/2}$, e ${\displaystyle 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 ${\displaystyle |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.

Referências