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 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.
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,
VertexFactory<V> vertexFactory,
Map<String,V> resultMap)
Generates a small-world graph.
|
public 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 nxn 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 parameterspublic void generateGraph(Graph<V,E> target, VertexFactory<V> vertexFactory, Map<String,V> resultMap)
generateGraph
in interface GraphGenerator<V,E,V>
target
- the target graphvertexFactory
- the vertex factoryresultMap
- not used by this generator, can be nullCopyright © 2017. All rights reserved.