org.graphstream.algorithm.generator

Class WattsStrogatzGenerator

java.lang.Object

org.graphstream.stream.SourceBase

org.graphstream.algorithm.generator.BaseGenerator

org.graphstream.algorithm.generator.WattsStrogatzGenerator

All Implemented Interfaces:

Generator, org.graphstream.stream.Source

public class WattsStrogatzGenerator
extends BaseGenerator

A generator following the small-world model of Watts and Strogatz.

This generator creates small-world graphs of arbitrary size.

This model generates a ring of n nodes where each node is connected to its k nearest neighbours in the ring (k/2 on each side, which means k must be even). Then it process each node of the ring in order following the ring, and "rewiring" each of their edges toward the not yet processed nodes with randomly chosen nodes with a probability beta.

Usage

You must provide values for n, k and beta at construction time. You must ensure that k is event, that n >> k >> log(n) >> 1. Furthermore, beta being a probability it must be between 0 and 1.

By default, the generator will produce a placement for nodes using the ``xyz`` attribute.

This generator will produce the ring of nodes once begin() has been called. Then calling nextEvents() will rewire one node at a time return true until each node is processed, in which case it returns false. You must then call end().

Example

 Graph graph = new SingleGraph("This is a small world!");
 Generator gen = new WattsStrogatzGenerator(20, 2, 0.5);
 
 gen.addSink(graph);
 gen.begin();
 while(gen.nextEvents()) {}
 gen.end();
 
 graph.display(false); // Node position is provided.
 

Reference

This generator is based on the Watts-Strogatz model.

Scientific Reference :

Watts, D.J. and Strogatz, S.H. "Collective dynamics of 'small-world' networks". Nature 393 (6684): 409–10. doi:10.1038/30918. PMID 9623998. 1998.

Nested Class Summary

Nested classes/interfaces inherited from class org.graphstream.stream.SourceBase

org.graphstream.stream.SourceBase.ElementType

Constructor Summary

Constructors

Constructor and Description
WattsStrogatzGenerator(int n, int k, double beta) New Watts-Strogatz generator.

Method Summary

Methods

Modifier and Type	Method and Description
void	begin() Begin the graph generation.
void	end() End the graph generation by finalizing it.
boolean	nextEvents() Perform the next step in generating the graph.

Methods inherited from class org.graphstream.algorithm.generator.BaseGenerator

addEdgeAttribute, addEdgeLabels, addNodeAttribute, addNodeLabels, isUsingInternalGraph, removeEdgeAttribute, removeNodeAttribute, setDirectedEdges, setEdgeAttributesRange, setNodeAttributesRange, setRandomSeed, setUseInternalGraph

Methods inherited from class org.graphstream.stream.SourceBase

addAttributeSink, addElementSink, addSink, attributeSinks, clearAttributeSinks, clearElementSinks, clearSinks, elementSinks, removeAttributeSink, removeElementSink, removeSink, sendAttributeChangedEvent, sendAttributeChangedEvent, sendEdgeAdded, sendEdgeAdded, sendEdgeAttributeAdded, sendEdgeAttributeAdded, sendEdgeAttributeChanged, sendEdgeAttributeChanged, sendEdgeAttributeRemoved, sendEdgeAttributeRemoved, sendEdgeRemoved, sendEdgeRemoved, sendGraphAttributeAdded, sendGraphAttributeAdded, sendGraphAttributeChanged, sendGraphAttributeChanged, sendGraphAttributeRemoved, sendGraphAttributeRemoved, sendGraphCleared, sendGraphCleared, sendNodeAdded, sendNodeAdded, sendNodeAttributeAdded, sendNodeAttributeAdded, sendNodeAttributeChanged, sendNodeAttributeChanged, sendNodeAttributeRemoved, sendNodeAttributeRemoved, sendNodeRemoved, sendNodeRemoved, sendStepBegins, sendStepBegins

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graphstream.stream.Source

addAttributeSink, addElementSink, addSink, clearAttributeSinks, clearElementSinks, clearSinks, removeAttributeSink, removeElementSink, removeSink

Constructor Detail

WattsStrogatzGenerator

public WattsStrogatzGenerator(int n,
                      int k,
                      double beta)

New Watts-Strogatz generator.

Parameters:

n - The number of nodes to generate.

k - The base degree of each node.

beta - Probability to "rewire" an edge.

Method Detail

begin

public void begin()

Description copied from interface: Generator

Begin the graph generation. This usually is the place for initialization of the generator. After calling this method, call the Generator.nextEvents() method to add elements to the graph.

nextEvents

public boolean nextEvents()

Description copied from interface: Generator

Perform the next step in generating the graph. While this method returns true, there are still more elements to add to the graph to generate it. Be careful that some generators never return false here, since they can generate graphs of arbitrary size. For such generators, simply stop calling this method when enough elements have been generated. A call to this method can produce an undetermined number of nodes and edges. Checking nodes count is advisable when generating the graph to avoid an unwanted big graph.

Returns:

true while there are elements to add to the graph.

end

public void end()

Description copied from class: BaseGenerator

End the graph generation by finalizing it. Once the Generator.nextEvents() method returned false (or even if you stop before), this method must be called to finish the graph. In addition, BaseGenerator adds a "clear" operations that removes all the kept edges and nodes identifiers and the associated data.

Specified by:

end in interface Generator

Overrides:

end in class BaseGenerator