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.