Class WattsStrogatzGraphGenerator<V,E>
 java.lang.Object

 org.jgrapht.generate.WattsStrogatzGraphGenerator<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
GraphGenerator<V,E,V>
public class WattsStrogatzGraphGenerator<V,E> extends Object implements GraphGenerator<V,E,V>
WattsStrogatz smallworld graph generator.The generator is described in the paper: D. J. Watts and S. H. Strogatz. Collective dynamics of smallworld networks. Nature 393(6684):440442, 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 clockwise around the ring, considering each vertex in turn until one lap is completed. Next, it considers the edges that connect vertices to their secondnearest 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 smallworld 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 rewiring. This variation was proposed in the paper: M. E. J. Newman and D. J. Watts, Renormalization group analysis of the smallworld network model, Physics Letters A, 263, 341, 1999.
 Author:
 Dimitrios Michail


Constructor Summary
Constructors Constructor Description WattsStrogatzGraphGenerator(int n, int k, double p)
ConstructorWattsStrogatzGraphGenerator(int n, int k, double p, boolean addInsteadOfRewire, Random rng)
ConstructorWattsStrogatzGraphGenerator(int n, int k, double p, long seed)
Constructor

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
generateGraph(Graph<V,E> target, Map<String,V> resultMap)
Generates a smallworld graph based on the WattsStrogatz 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 nodesk
 connect each node to its k nearest neighbors in a ringp
 the probability of rewiring 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 nodesk
 connect each node to its k nearest neighbors in a ringp
 the probability of rewiring each edgeseed
 seed for the random number generator Throws:
IllegalArgumentException
 in case of invalid parameters

WattsStrogatzGraphGenerator
public WattsStrogatzGraphGenerator(int n, int k, double p, boolean addInsteadOfRewire, Random rng)
Constructor Parameters:
n
 the number of nodesk
 connect each node to its k nearest neighbors in a ringp
 the probability of rewiring each edgeaddInsteadOfRewire
 whether to add shortcut edges instead of rewiringrng
 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 smallworld graph based on the WattsStrogatz model. Specified by:
generateGraph
in interfaceGraphGenerator<V,E,V>
 Parameters:
target
 the target graphresultMap
 not used by this generator, can be null

