org.jgrapht.generate

## Class WattsStrogatzGraphGenerator<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
GraphGenerator<V,E,V>

public class WattsStrogatzGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>
Watts-Strogatz small-world graph generator.

The generator is described in the paper: D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature 393(6684):440--442, 1998.

The following paragraph from the paper describes the construction.

"The generator starts with a ring of $n$ vertices, each connected to its $k$ nearest neighbors ($k$ must be even). Then it chooses a vertex and the edge that connects it to its nearest neighbor in a clockwise sense. With probability $p$, it reconnects this edge to a vertex chosen uniformly at random over the entire ring with duplicate edges forbidden; otherwise it leaves the edge in place. The process is repeated by moving clock-wise around the ring, considering each vertex in turn until one lap is completed. Next, it considers the edges that connect vertices to their second-nearest neighbors clockwise. As before, it randomly rewires each of these edges with probability $p$, and continues this process, circulating around the ring and proceeding outward to more distant neighbors after each lap, until each edge in the original lattice has been considered once. As there are $\frac{nk}{2}$ edges in the entire graph, the rewiring process stops after $\frac{k}{2}$ laps. For $p = 0$, the original ring is unchanged; as $p$ increases, the graph becomes increasingly disordered until for $p = 1$, all edges are rewired randomly. For intermediate values of $p$, the graph is a small-world network: highly clustered like a regular graph, yet with small characteristic path length, like a random graph."

The authors require $n \gg k \gg \ln(n) \gg 1$ and specifically $k \gg \ln(n)$ guarantees that a random graph will be connected.

Through the constructor parameter the model can be slightly changed into adding shortcut edges instead of re-wiring. This variation was proposed in the paper: M. E. J. Newman and D. J. Watts, Renormalization group analysis of the small-world network model, Physics Letters A, 263, 341, 1999.

Author:
Dimitrios Michail
• ### Constructor Summary

Constructors
Constructor and Description
WattsStrogatzGraphGenerator(int n, int k, double p)
Constructor
WattsStrogatzGraphGenerator(int n, int k, double p, boolean addInsteadOfRewire, Random rng)
Constructor
WattsStrogatzGraphGenerator(int n, int k, double p, long seed)
Constructor
• ### Method Summary

All Methods
Modifier and Type Method and Description
void generateGraph(Graph<V,E> target, Map<String,V> resultMap)
Generates a small-world graph based on the Watts-Strogatz model.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Methods inherited from interface org.jgrapht.generate.GraphGenerator

generateGraph
• ### Constructor Detail

• #### WattsStrogatzGraphGenerator

public WattsStrogatzGraphGenerator(int n,
int k,
double p)
Constructor
Parameters:
n - the number of nodes
k - connect each node to its k nearest neighbors in a ring
p - the probability of re-wiring each edge
Throws:
IllegalArgumentException - in case of invalid parameters
• #### WattsStrogatzGraphGenerator

public WattsStrogatzGraphGenerator(int n,
int k,
double p,
long seed)
Constructor
Parameters:
n - the number of nodes
k - connect each node to its k nearest neighbors in a ring
p - the probability of re-wiring each edge
seed - seed for the random number generator
Throws:
IllegalArgumentException - in case of invalid parameters
• #### WattsStrogatzGraphGenerator

public WattsStrogatzGraphGenerator(int n,
int k,
double p,
Random rng)
Constructor
Parameters:
n - the number of nodes
k - connect each node to its k nearest neighbors in a ring
p - the probability of re-wiring each edge
addInsteadOfRewire - whether to add shortcut edges instead of re-wiring
rng - the random number generator to use
Throws:
IllegalArgumentException - in case of invalid parameters
• ### Method Detail

• #### generateGraph

public void generateGraph(Graph<V,E> target,
Map<String,V> resultMap)
Generates a small-world graph based on the Watts-Strogatz model.
Specified by:
generateGraph in interface GraphGenerator<V,E,V>
Parameters:
target - the target graph
resultMap - not used by this generator, can be null