org.jgrapht.generate

## Class KleinbergSmallWorldGraphGenerator<V,E>

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

public class KleinbergSmallWorldGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>
Kleinberg's small-world graph generator.

The generator is described in the paper: J. Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, in Proc. 32nd ACM Symp. Theory of Comp., 163-170, 2000.

The basic structure is a a two-dimensional grid and allows for edges to be directed. It begins with a set of nodes (representing individuals in the social network) that are identified with the set of lattice points in an n x n square. For a universal constant p >= 1, the node u has a directed edge to every other node within lattice distance p (these are its local contacts). For universal constants q >= 0 and r >= 0, we also construct directed edges from u to q other nodes (the long-range contacts) using independent random trials; the i-th directed edge from u has endpoint v with probability proportional to 1/d(u,v)^r where d(u,v) is the lattice distance from u to v.

Since:
February 2017
Author:
Dimitrios Michail
• ### Constructor Summary

Constructors
Constructor and Description
KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r)
Constructor
KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r, long seed)
Constructor
KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r, Random rng)
Constructor
• ### Method Summary

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

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### KleinbergSmallWorldGraphGenerator

public KleinbergSmallWorldGraphGenerator(int n,
int p,
int q,
int r)
Constructor
Parameters:
n - generate set of lattice points in a n by n square
p - lattice distance for which each node is connected to every other node in the lattice (local connections)
q - how many long-range contacts to add for each node
r - probability distribution parameter which is a basic structural parameter measuring how widely "networked" the underlying society of nodes is
Throws:
IllegalArgumentException - in case of invalid parameters
• #### KleinbergSmallWorldGraphGenerator

public KleinbergSmallWorldGraphGenerator(int n,
int p,
int q,
int r,
long seed)
Constructor
Parameters:
n - generate set of lattice points in a n by n square
p - lattice distance for which each node is connected to every other node in the lattice (local connections)
q - how many long-range contacts to add for each node
r - probability distribution parameter which is a basic structural parameter measuring how widely "networked" the underlying society of nodes is
seed - seed for the random number generator
Throws:
IllegalArgumentException - in case of invalid parameters
• #### KleinbergSmallWorldGraphGenerator

public KleinbergSmallWorldGraphGenerator(int n,
int p,
int q,
int r,
Random rng)
Constructor
Parameters:
n - generate set of lattice points in a nxn square
p - lattice distance for which each node is connected to every other node in the lattice (local connections)
q - how many long-range contacts to add for each node
r - probability distribution parameter which is a basic structural parameter measuring how widely "networked" the underlying society of nodes is
rng - the random number generator to use
Throws:
IllegalArgumentException - in case of invalid parameters
• ### Method Detail

• #### generateGraph

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