Package org.graph4j.generators

Class WattsStrogatzGenerator

java.lang.Object

org.graph4j.generators.AbstractGraphGenerator

org.graph4j.generators.WattsStrogatzGenerator

public class WattsStrogatzGenerator
extends AbstractGraphGenerator

The Watts–Strogatz model produces graphs with small-world properties, including short average path lengths and high clustering. Consider the desired number of vertices n and their mean degree k. Construct a regular ring lattice, that is a graph with n vertices each connected to k neighbors, k/2 on each side. For every vertex v, take every edge (v,u) connecting v to its k/2 rightmost neighbors, and rewire it with a given probability. Rewiring is done by replacing the edge (v,u) with (v,w) where w is chosen uniformly at random from all possible vertices, avoiding self-loops and duplicate edges. It is also possible to create supplementary new edges, instead or in addition to rewiring.

Bibliography: D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature 393(6684):440--442, 1998. M. E. J. Newman and D. J. Watts, Renormalization group analysis of the small-world network model, Physics Letters A, 263, 341, 1999.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.generators.AbstractGraphGenerator

vertices

Constructor Summary

Constructors

Constructor	Description
WattsStrogatzGenerator(int numVertices, int averageDegree, double rewireProbability, double addProbability)
WattsStrogatzGenerator(int firstVertex, int lastVertex, int degree, double rewireProbability, double addProbability)

Method Summary

Modifier and Type	Method	Description
Graph	createGraph()

Methods inherited from class org.graph4j.generators.AbstractGraphGenerator

addRandomEdges

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

WattsStrogatzGenerator

public WattsStrogatzGenerator(int numVertices,
 int averageDegree,
 double rewireProbability,
 double addProbability)

Parameters:

numVertices - the number of vertices.

averageDegree - the average degree of the vertices (the number of k-nearest neighbors).

rewireProbability - the probability to rewire an edge.

addProbability - the probability to add a new edge (use 0 for the original model).

WattsStrogatzGenerator

public WattsStrogatzGenerator(int firstVertex,
 int lastVertex,
 int degree,
 double rewireProbability,
 double addProbability)

Parameters:

firstVertex - the number of the first vertex in the generated graph.

lastVertex - the number of the last vertex in the generated graph.

degree - the average degree of the vertices (the number of k-nearest neighbors).

rewireProbability - the probability to rewire an edge.

addProbability - the probability to add a new edge (use 0 for the original model).

Method Details

createGraph

public Graph createGraph()

Returns:

a random Watts-Strogatz network.