navigable_small_world_graph¶
-
navigable_small_world_graph
(n, p=1, q=1, r=2, dim=2, seed=None)[source]¶ Return a navigable small-world graph.
A navigable small-world graph is a directed grid with additional long-range connections that are chosen randomly.
[...] we begin with a set of nodes [...] that are identified with the set of lattice points in an \(n \times n\) square, \(\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}\), and we define the lattice distance between two nodes
(i, j)
and(k, l)
to be the number of “lattice steps” separating them:d((i, j), (k, l)) = |k - i| + |l - j|
.For a universal constant
p >= 1
, the nodeu
has a directed edge to every other node within lattice distancep
— these are its local contacts. For universal constantsq >= 0
andr >= 0
we also construct directed edges fromu
toq
other nodes (the long-range contacts) using independent random trials; thei`th directed edge from `u
has endpointv
with probability proportional to[d(u,v)]^{-r}
.—[1]
Parameters: - n (int) – The number of nodes.
- p (int) – The diameter of short range connections. Each node is joined with every other node within this lattice distance.
- q (int) – The number of long-range connections for each node.
- r (float) – Exponent for decaying probability of connections. The probability of
connecting to a node at lattice distance
d
is1/d^r
. - dim (int) – Dimension of grid
- seed (int, optional) – Seed for random number generator (default=None).
References
[1] J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.