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 small-world graph.
A navigable small-world graph is a directed grid with additional long-range connections that are chosen randomly. From [R291]:
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 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\), the node \(u\) has a directed edge to every other node within lattice distance \(p\) (local contacts) .
For universal constants \(q\ge 0\) and \(r\ge 0\) construct directed edges from \(u\) to \(q\) other nodes (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}\).
Parameters : n : int
The number of nodes.
p : int
The diameter of short range connections. Each node is connected to every other node within lattice distance p.
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
[R291] (1, 2) J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.