GraphTheory[RandomGraphs] - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : RandomGraphs : GraphTheory/RandomGraphs/WattsStrogatzGraph

GraphTheory[RandomGraphs]

 WattsStrogatzGraph
 generate Watts-Strogatz random graph

 Calling Sequence WattsStrogatzGraph(n,p,k,options)

Parameters

 n - positive integer p - numeric value between 0.0 and 1.0 k - (optional) positive integer, by default 2 options - (optional) equation(s) of the form seed=value

Options

 • seed : integer or none
 Seed for the random number generator. Equivalent to calling randomize(seed) immediately before invoking this function.

Description

 • WattsStrogatzGraph(n,p,k,options) creates a Watts-Strogatz random graph on n vertices.
 • The random number generator used can be seeded using the seed option or the randomize function.

Definition

 • A Watts-Strogatz random graph is a circulant graph with parameters n and k in which each edge has been rewired with probability p.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $G≔\mathrm{WattsStrogatzGraph}\left(8,0.5\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 8 vertices and 14 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$

The DegreeSequence command returns the degrees of the vertices of a given graph.

 > $\mathrm{DegreeSequence}\left(G\right)$
 $\left[{3}{,}{5}{,}{2}{,}{3}{,}{3}{,}{5}{,}{4}{,}{3}\right]$ (2)
 > $G≔\mathrm{WattsStrogatzGraph}\left(100,0.25,3\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 100 vertices and 300 edge\left(s\right)}}$ (3)

To view the degree distribution of a Watts-Strogatz graph:

 > $\mathrm{Statistics}:-\mathrm{Histogram}\left(\mathrm{DegreeSequence}\left(G\right)\right)$
 > $\mathrm{Statistics}:-\mathrm{Tally}\left(\mathrm{DegreeSequence}\left(G\right)\right)$
 $\left[{4}{=}{6}{,}{5}{=}{22}{,}{6}{=}{43}{,}{7}{=}{24}{,}{8}{=}{5}\right]$ (4)

References

 Watts, D. J.; Strogatz, S. H. (1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. (4 June 1998). doi:10.1038/30918. PMID 9623998.

Compatibility

 • The GraphTheory[RandomGraphs][WattsStrogatzGraph] command was introduced in Maple 2019.