navigable_small_world_graph

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

返回一个可导航的小世界图。

可导航的小世界图是一个带附加长程随机连接的定向网格图。

[...] 我们从一组节点 [...] 开始，这些节点与 \(n \times n\) 正方形中的格点集 \(\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}\) 相对应，我们定义两个节点 \((i, j)\) 和 \((k, l)\) 之间的格点距离为分隔它们的“格点步数”：\(d((i, j), (k, l)) = |k - i| + |l - j|\)。

对于一个通用常数 \(p >= 1\)，节点 \(u\) 与格点距离在 \(p\) 之内的所有其他节点都有一条有向边——这些是它的本地联系。对于通用常数 \(q >= 0\) 和 \(r >= 0\)，我们还通过独立的随机试验从 \(u\) 到其他 \(q\) 个节点构建有向边（长程联系）；从 :math:`u` 的第 \(i\) 条有向边的终点 \(v\) 的概率与 \([d(u,v)]^{-r}\) 成正比。

—[1]

参数:

nint

格点一边的长度；因此图中节点的数量是 \(n^2\)。

pint

短程连接的直径。每个节点与其格点距离在此范围内的所有其他节点连接。

qint

每个节点的长程连接数量。

rfloat

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

dimint

网格的维度

seedinteger, random_state, 或 None (default)

随机数生成状态的指示。参见 随机性。

参考文献

[1]

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