Class KleinbergSmallWorldGraphGenerator<V,​E>

• java.lang.Object
• org.jgrapht.generate.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 java.lang.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 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, java.util.Random rng) Constructor • Method Summary All Methods Modifier and Type Method Description void generateGraph​(Graph<V,​E> target, java.util.Map<java.lang.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: java.lang.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: java.lang.IllegalArgumentException - in case of invalid parameters • KleinbergSmallWorldGraphGenerator public KleinbergSmallWorldGraphGenerator​(int n, int p, int q, int r, java.util.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:
java.lang.IllegalArgumentException - in case of invalid parameters
• Method Detail

• generateGraph

public void generateGraph​(Graph<V,​E> target,
java.util.Map<java.lang.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