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

navigable_small_world_graph
(n, p=1, q=1, r=2, dim=2, seed=None)[source]¶ Return a navigable smallworld graph.
A navigable smallworld graph is a directed grid with additional longrange connections that are chosen randomly.
[...] we begin with a set of nodes [...] that are identified with the set of lattice points in an square, , and we define the lattice distance between two nodes and to be the number of “lattice steps” separating them: . For a universal constant , the node has a directed edge to every other node within lattice distance — these are its local contacts. For universal constants and we also construct directed edges from to other nodes (the longrange contacts) using independent random trials; the has endpoint with probability proportional to .
—[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 longrange connections for each node.
 r (float) – Exponent for decaying probability of connections. The probability of connecting to a node at lattice distance is .
 dim (int) – Dimension of grid
 seed (int, optional) – Seed for random number generator (default=None).
References
[1] J. Kleinberg. The smallworld phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.