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 imes 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 \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 \ge 0$ and $r \ge 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 $[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$ is $1/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.