navigable_small_world_graph

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

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

可导航的小世界图是一个带有额外随机选择的长距离连接的有向网格。

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

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

—[1]

Parameters:

nint

网格一侧的长度；图中节点的数量因此为:math:n^2。

pint

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

qint

每个节点的长距离连接数。

rfloat

连接概率衰减的指数。连接到网格距离:math:d`的节点的概率为:math:`1/d^r。

dimint

网格的维度

seedinteger, random_state, 或 None (默认)

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

References

[1]

10. Kleinberg. 小世界现象：一种算法视角。第32届ACM计算理论研讨会论文集，2000年。