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 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 \(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 longrange 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 longrange 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 smallworld phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.