navigable_small_world_graph

navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None)

返回可导航的小世界图。

一个可导航的小世界图是一个有向的网格，其中包含随机选择的附加远程连接。

[...] 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|\).

对于万能常量 \(p >= 1\) ，该节点 \(u\) 具有指向晶格距离内所有其他节点的有向边 \(p\) -这些是它的 本地联系人 。对于万能常量 \(q >= 0\) 和 \(r >= 0\) 我们还从以下位置构造有向边 \(u\) 至 \(q\) 其他节点( long-range contacts )使用独立随机试验； \(i\) 此有向边来自 \(u\) 具有端点 \(v\) 与概率成正比 \([d(u,v)]^{{-r}}\) 。

—[1]

参数

n集成

点阵一侧的长度；因此，图中的节点数为 \(n^2\) 。

p集成

短程连接的直径。每个节点都与该晶格距离内的所有其他节点连接。

q集成

每个节点的远程连接数。

r浮动

连接的衰减概率的指数。连接到格点距离上的节点的概率 \(d\) 是 \(1/d^r\) 。

dim集成

栅格尺寸

seed整数、随机状态或无（默认）

随机数生成状态的指示器。见 Randomness .

工具书类

1

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