Module org.jgrapht.core
Package 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 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 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