networkx.generators.geometric.navigable_small_world_graph¶

networkx.generators.geometric.navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None)¶

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 [R165]:

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

[R165]

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

Previous topic

Next topic

networkx.generators.geometric.navigable_small_world_graph¶

Navigation

Previous topic

Next topic

Quick search

networkx.generators.geometric.navigable_small_world_graph¶

Navigation