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$. Since: February 2017 Author: Dimitrios Michail • 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