random_kernel_graph#

random_kernel_graph(n, kernel_integral, kernel_root=None, seed=None, *, create_using=None)[源代码]#

基于指定的核函数返回一个随机图。

该算法通过核函数 \(\kappa(x,y)\) 指定的概率 [1] 来选择 \([n(n-1)]/2\) 个可能的每条边。核函数 \(\kappa(x,y)\) 必须是对称的（关于 \(x,y\)），非负且有界的函数。

参数:

nint: 节点数
kernel_integralfunction: 返回核函数 \(\kappa(x,y)\) 的定积分的函数，即 \(F(y,a,b) := \int_a^b \kappa(x,y)dx\)
kernel_root: function (可选): 返回方程 \(F(y,a,b) = r\) 的根 \(b\) 的函数。如果为 None，则使用 scipy.optimize.brentq() 查找根（这需要 SciPy）。
seedinteger, random_state, 或 None (默认): 随机数生成状态的指示。参见随机性。
create_usingGraph constructor, 可选 (默认=nx.Graph): 要创建的图类型。如果提供的是图实例，则在填充前会被清空。不支持多重图和有向图类型，如果指定这些类型会引发 NetworkXError。

另见

gnp_random_graph
expected_degree_graph

备注

核函数通过其定积分指定，定积分必须作为参数提供。如果核积分及其根可以在 \(O(1)\) 时间内找到，则此算法的运行时间为 \(O(n+m)\)，其中 m 是期望的边数 [2]。

节点被设置为从 \(0\) 到 \(n-1\) 的整数。

参考文献

[1]

Bollobás, Béla, Janson, S., and Riordan, O. "The phase transition in inhomogeneous random graphs", Random Structures Algorithms, 31, 3–122, 2007。

[2]

Hagberg A, Lemons N (2015), "Fast Generation of Sparse Random Kernel Graphs". PLoS ONE 10(9): e0135177, 2015. doi:10.1371/journal.pone.0135177

示例

生成一个 Erdős–Rényi 随机图 \(G(n,c/n)\)，使用核函数 \(\kappa(x,y)=c\)，其中 \(c\) 是平均期望度。

>>> def integral(u, w, z):
...     return c * (z - w)
>>> def root(u, w, r):
...     return r / c + w
>>> c = 1
>>> graph = nx.random_kernel_graph(1000, integral, root)