Enter search terms or a module, class or function name.
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
p : int
q : int
r : float
dim : int
seed : int, optional
|
---|
References
[R291] | (1, 2) J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. |