Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Construir Watts-Strogatz Small World Graph modelo

Este ejemplo muestra cómo construir y analizar un gráfico de mundo pequeño Watts-Strogatz. El modelo Watts-Strogatz es un gráfico aleatorio que tiene propiedades de red de pequeño mundo, como clustering y longitud de trayecto promedio corto.

Descripción del algoritmo

La creación de un gráfico Watts-Strogatz tiene dos pasos básicos:

  1. Crea una enrejado de anillos con nodos de grado medio . Cada nodo está conectado a su vecinos más cercanos a ambos lados.

  2. Para cada arista del gráfico, vuelva a conectar el nodo de destino con la probabilidad . El borde recableado no puede ser un duplicado o auto-loop.

Después del primer paso, el gráfico es una celosía de anillos perfecta. Así que cuando , no se vuelve a cablear ningún borde y el modelo devuelve una retícula de anillo. Por el contrario, cuando , todos los bordes se recablean y la celosía del anillo se transforma en un gráfico aleatorio.

El archivo implementa este algoritmo de gráfico para gráficos no dirigidos.WattsStrogatz.m Los parámetros de entrada son, y de acuerdo con la descripción del algoritmo anterior.NKbeta

Ver el archivo.WattsStrogatz.m

  % Copyright 2015 The MathWorks, Inc.  function h = WattsStrogatz(N,K,beta) % H = WattsStrogatz(N,K,beta) returns a Watts-Strogatz model graph with N % nodes, N*K edges, mean node degree 2*K, and rewiring probability beta. % % beta = 0 is a ring lattice, and beta = 1 is a random graph.  % Connect each node to its K next and previous neighbors. This constructs % indices for a ring lattice. s = repelem((1:N)',1,K); t = s + repmat(1:K,N,1); t = mod(t-1,N)+1;  % Rewire the target node of each edge with probability beta for source=1:N         switchEdge = rand(K, 1) < beta;          newTargets = rand(N, 1);     newTargets(source) = 0;     newTargets(s(t==source)) = 0;     newTargets(t(source, ~switchEdge)) = 0;          [~, ind] = sort(newTargets, 'descend');     t(source, switchEdge) = ind(1:nnz(switchEdge)); end  h = graph(s,t); end  

Ring Lattice

Construya una celosía de anillos con 500 nodos utilizando la función.WattsStrogatz Cuando es 0, la función devuelve una celosía de anillo cuyos nodos tienen todos los grados.beta2K

h = WattsStrogatz(500,25,0); plot(h,'NodeColor','k','Layout','circle'); title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0$', ...     'Interpreter','latex') 

Algunos bordes aleatorios

Aumente la cantidad de aleatoriedad en el gráfico elevando y.beta0.150.50

h2 = WattsStrogatz(500,25,0.15); plot(h2,'NodeColor','k','EdgeAlpha',0.1); title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0.15$', ...     'Interpreter','latex') 

h3 = WattsStrogatz(500,25,0.50); plot(h3,'NodeColor','k','EdgeAlpha',0.1); title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0.50$', ...     'Interpreter','latex') 

Random Graph

Genere un gráfico completamente aleatorio incrementando su valor máximo.beta1.0 Esto reconecta todos los bordes.

h4 = WattsStrogatz(500,25,1); plot(h4,'NodeColor','k','EdgeAlpha',0.1); title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 1$', ...     'Interpreter','latex') 

Distribución de grado

La distribución de grados de los nodos en los diferentes gráficos Watts-Strogatz varía. Cuando es 0, todos los nodos tienen el mismo grado, por lo que la distribución de grados es sólo una función Dirac-delta centrada en,beta2K2K . Sin embargo, a medida que aumenta, la distribución de grado cambia.beta

Esta gráfica muestra las distribuciones de grado para los valores distintos de cero de.beta

histogram(degree(h2),'BinMethod','integers','FaceAlpha',0.9); hold on histogram(degree(h3),'BinMethod','integers','FaceAlpha',0.9); histogram(degree(h4),'BinMethod','integers','FaceAlpha',0.8); hold off title('Node degree distributions for Watts-Strogatz Model Graphs') xlabel('Degree of node') ylabel('Number of nodes') legend('\beta = 1.0','\beta = 0.50','\beta = 0.15','Location','NorthWest') 

Formación Hub

El gráfico Watts-Strogatz tiene un alto coeficiente de clustering, por lo que los nodos tienden a formar cliques, o grupos pequeños de nodos estrechamente interconectados. Como aumentos hacia su valor máximo de, se ve un número cada vez mayor de nodos de concentrador, o nodos de alto grado relativo.beta1.0 Los hubs son una conexión común entre otros nodos y entre los camarillas en el gráfico. La existencia de hubs es lo que permite la formación de camarillas preservando una longitud de trayecto media corta.

Calcule la longitud media del trayecto y el número de nodos del concentrador para cada valor de.beta Para los fines de este ejemplo, los nodos del concentrador son nodos con un grado mayor o igual que 55. Estos son todos los nodos cuyo grado aumentó 10% o más en comparación con la celosía del anillo original.

n = 55; d = [mean(mean(distances(h))), nnz(degree(h)>=n); ...      mean(mean(distances(h2))), nnz(degree(h2)>=n); ...      mean(mean(distances(h3))), nnz(degree(h3)>=n);      mean(mean(distances(h4))), nnz(degree(h4)>=n)]; T = table([0 0.15 0.50 1]', d(:,1), d(:,2),...     'VariableNames',{'Beta','AvgPathLength','NumberOfHubs'}) 
 T =    4x3 table      Beta    AvgPathLength    NumberOfHubs     ____    _____________    ____________         0         5.48              0          0.15       2.0715             20           0.5       1.9101             85             1       1.9008             92       

A medida que aumenta, la longitud de trayecto promedio en el gráfico cae rápidamente a su valor límite.beta Esto es debido a la formación de los nodos del concentrador altamente conectados, que se hacen más numerosos como aumentos.beta

Trace el Gráfico de modelo Watts-Strogatz, que hace que el tamaño y el color de cada nodo sean proporcionales a su grado. Esta es una manera eficaz de visualizar la formación de hubs.

colormap hsv deg = degree(h2); nSizes = 2*sqrt(deg-min(deg)+0.2); nColors = deg; plot(h2,'MarkerSize',nSizes,'NodeCData',nColors,'EdgeAlpha',0.1) title('Watts-Strogatz Graph with $N = 500$ nodes, $K = 25$, and $\beta = 0.15$', ...     'Interpreter','latex') colorbar 

Consulte también

|