Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# networkx.generators.geometric.navigable_small_world_graph¶

navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None)[source]

Returns 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 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$$ has endpoint $$v$$ with probability proportional to $$[d(u,v)]^{-r}$$.

[1]

Parameters: n (int) – The length of one side of the lattice; the number of nodes in the graph is therefore $$n^2$$. 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 (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.

References

 [1] J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.