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 x n square. For a universal constant p >= 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 >= 0 and r >= 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 1/d(u,v)^r where d(u,v) is the lattice distance from u to v.

Since:

February 2017

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

Modifier and Type	Method and Description
void	generateGraph(Graph<V,E> target, VertexFactory<V> vertexFactory, 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

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 nxn 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,
                          VertexFactory<V> vertexFactory,
                          Map<String,V> resultMap)

Generates a small-world graph.

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - the target graph

vertexFactory - the vertex factory

resultMap - not used by this generator, can be null