Note: This page has been translated by MathWorks. Please click here

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

This example shows how to construct and analyze a Watts-Strogatz small-world graph. The Watts-Strogatz model is a random graph that has small-world network properties, such as clustering and short average path length.

Creating a Watts-Strogatz graph has two basic steps:

Create a ring lattice with nodes of mean degree . Each node is connected to its nearest neighbors on either side.

For each edge in the graph, rewire the target node with probability . The rewired edge cannot be a duplicate or self-loop.

After the first step the graph is a perfect ring lattice. So when , no edges are rewired and the model returns a ring lattice. In contrast, when , all of the edges are rewired and the ring lattice is transformed into a random graph.

The file `WattsStrogatz.m`

implements this graph algorithm for undirected graphs. The input parameters are `N`

, `K`

, and `beta`

according to the algorithm description above.

View the file `WattsStrogatz.m`

.

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 % Copyright 2015 The MathWorks, Inc.

Construct a ring lattice with 500 nodes using the `WattsStrogatz`

function. When `beta`

is 0, the function returns a ring lattice whose nodes all have degree `2K`

.

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')

Increase the amount of randomness in the graph by raising `beta`

to `0.15`

and `0.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')

Generate a completely random graph by increasing `beta`

to its maximum value of `1.0`

. This rewires all of the edges.

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')

The degree distribution of the nodes in the different Watts-Strogatz graphs varies. When `beta`

is 0, the nodes all have the same degree, `2K`

, so the degree distribution is just a Dirac-delta function centered on `2K`

, . However, as `beta`

increases, the degree distribution changes.

This plot shows the degree distributions for the nonzero values of `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')

The Watts-Strogatz graph has a high clustering coefficient, so the nodes tend to form cliques, or small groups of closely interconnected nodes. As `beta`

increases towards its maximum value of `1.0`

, you see an increasingly large number of hub nodes, or nodes of high relative degree. The hubs are a common connection between other nodes and between cliques in the graph. The existence of hubs is what permits the formation of cliques while preserving a short average path length.

Calculate the average path length and number of hub nodes for each value of `beta`

. For the purposes of this example, the hub nodes are nodes with degree greater than or equal to 55. These are all of the nodes whose degree increased 10% or more compared to the original ring lattice.

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

As `beta`

increases, the average path length in the graph quickly falls to its limiting value. This is due to the formation of the highly connected hub nodes, which become more numerous as `beta`

increases.

Plot the Watts-Strogatz model graph, making the size and color of each node proportional to its degree. This is an effective way to visualize the formation of 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

Was this topic helpful?