V - the graph vertex typeE - the graph edge typepublic class KleinbergSmallWorldGraphGenerator<V,E> extends Object implements GraphGenerator<V,E,V>
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$.
| 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
|
| Modifier and Type | Method and Description |
|---|---|
void |
generateGraph(Graph<V,E> target,
Map<String,V> resultMap)
Generates a small-world graph.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitgenerateGraphpublic KleinbergSmallWorldGraphGenerator(int n,
int p,
int q,
int r)
n - generate set of lattice points in a $n$ by $n$ squarep - 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 noder - probability distribution parameter which is a basic structural parameter measuring
how widely "networked" the underlying society of nodes isIllegalArgumentException - in case of invalid parameterspublic KleinbergSmallWorldGraphGenerator(int n,
int p,
int q,
int r,
long seed)
n - generate set of lattice points in a $n$ by $n$ squarep - 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 noder - probability distribution parameter which is a basic structural parameter measuring
how widely "networked" the underlying society of nodes isseed - seed for the random number generatorIllegalArgumentException - in case of invalid parameterspublic KleinbergSmallWorldGraphGenerator(int n,
int p,
int q,
int r,
Random rng)
n - generate set of lattice points in a $n \times n$ squarep - 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 noder - probability distribution parameter which is a basic structural parameter measuring
how widely "networked" the underlying society of nodes isrng - the random number generator to useIllegalArgumentException - in case of invalid parametersCopyright © 2019. All rights reserved.