Usuário(a):MikeFoto/Testes

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

O modelo de Watts-Strogatz é um modelo de geração de grafos aleatórios com propriedades de pequeno mundo, com comprimentos médios de trajeto curtos e um grande agrupamento . Foi proposto por Duncan J. Watts e Steven Strogatz no seu artigo conjunto publicado na Nature em 1998 . O modelo também ficou conhecido como o (Watts) modelo beta depois Watts ter usado β para formulá-la no seu livro de ciência popular Six Degrees.

Justificativo para o modelo

O estudo formal dos grafos aleatórios remonta ao trabalho de Paul Erdös e Alfred Rényi . Os grafos que eles consideraram, são agora conhecidos como grafos clássicos ou grafos de 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 nem aglomeração local nem 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 baixo coeficiente de agrupamento.
2. Eles não contam para a formação de hubs. Formalmente, o grau de distribuição dos 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 livres de escala.

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

Watts–Strogatz graph

Dado o número desejado de $N$ nós, o médio $K$ (assumido como sendo um inteiro par) e um especial de parâmetro β, satisfazendo $0\leq \beta \leq 1$ e $N\gg K\gg ln(N)\gg 1$, o modelo constrói um grafo dirigido 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 $\beta$. 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\neq 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 agrupamentos no local, e os links aleatórios reduzem drasticamente o comprimento médio dos caminhos. O algoritmo apresenta-se sobre $\beta {\frac {NK}{2}}$ arestas não treliçadas. Variando $\beta$ torna possível interpolar entre uma rede regular ($\beta =0$) e um grafo aleatório ($\beta =1$) aproximando-se do grafo aleatório de 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 agrupamento, e o grau de distribuição.

Comprimento do caminho médio

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 $\beta \rightarrow 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<\beta <1$ o comprimento do caminho médio cai muito rapidamente com o aumento de $\beta$, aproximando-se rapidamente do seu valor limite.

Coeficiente de agrupamento

Para o anel treliça o Coeficiente de agrupamento $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 $\beta \rightarrow 1$ o coeficiente de agrupamento 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 agrupamento continua muito perto do seu valor para a rede regular, e só desce relativamente ao $\beta$ alto. Isso resulta numa região onde o caminho médio desce rapidamente, mas o coeficiente de agrupamento não, explica-se o fenómeno de "pequeno mundo".

Se utilizar a medida Barrat e Weigt para o agrupamento $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}.$

Grau de Distribuição

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 $\beta \rightarrow 1$ é a distribuição de Poisson, como com os grafos clássicos. A distribuição grau para $0<\beta <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 grau de distribuição de grau irrealista. Em contraste, as redes reais são muitas das vezes redes livres de escala heterogéneas em grau, com “hubs” e um grau de distribuição sem escala. 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 agrupamento 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 (BA) 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.

See also

• propriedades de pequeno mundo
• Modelo Erdös-Rényi
• modelo Barabási-Albert
• Redes Sociais