Module org.jgrapht.core
Package org.jgrapht.generate

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 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 Details

    • 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 Details

    • 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