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 \times n$ square. For a universal constant $p \geq 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 \geq 0$ and $r \geq 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 \frac{1}{d(u,v)^r}$where$d(u,v)$is the lattice distance from$u$to$v$. 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, 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 • ### Methods inherited from interface org.jgrapht.generate.GraphGenerator generateGraph • ### 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$n \times 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
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.
Specified by:
generateGraph in interface GraphGenerator<V,E,V>
Parameters:
target - the target graph
resultMap - not used by this generator, can be null