networkx.navigable_small_world_graph¶

networkx.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 \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`th directed edge from `u has endpoint v with probability proportional to [d(u,v)]^{-r}.

—[R1197]

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

[R1197]

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