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,\dots ,n\},j\in \{1,2,\dots ,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‘thdirectededgefrom:math:‘u$ has endpoint $v$ with probability proportional to $[d(u,v){]}^{-r}$.

—[1]

Parameters:

nint

The length of one side of the lattice; the number of nodes in the graph is therefore $n^2$.

pint

The diameter of short range connections. Each node is joined with every other node within this lattice distance.

qint

The number of long-range connections for each node.

rfloat

Exponent for decaying probability of connections. The probability of connecting to a node at lattice distance $d$ is $1/d^r$.

dimint

Dimension of grid

seedinteger, 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.