5.5.13. networkx.generators.random_graphs.random_kernel_graph¶

networkx.generators.random_graphs.random_kernel_graph(n, kernel_integral, kernel_root=None, seed=None)[source]¶

Return an random graph based on the specified kernel.

The algorithm chooses each of the [n(n-1)]/2 possible edges with probability specified by a kernel kappa(x,y) [R1086]. The kernel kappa(x,y) must be a symmetric (in x,y), non-negative, bounded function.

Parameters:

n : int The number of nodes kernal_integral : function Function that returns the definite integral of the kernel kappa(x,y), F(y,a,b) := int_a^b kappa(x,y)dx kernel_root: function (optional) Function that returns the root b of the equation F(y,a,b) = r. If None, the root is found using scipy.optimize.brentq() (this requires SciPy). seed : int, optional Seed for random number generator (default=None)

See also

gnp_random_graph, expected_degree_graph

Notes

The kernel is specified through its definite integral which must be provided as one of the arguments. If the integral and root of the kernel integral can be found in O(1) time then this algorithm runs in time O(n+m) where m is the expected number of edges [R1087].

The nodes are set to integers from 0 to n-1.

References

[R1086]

(1, 2) Bollobás, Béla, Janson, S. and Riordan, O. “The phase transition in inhomogeneous random graphs”, Random Structures Algorithms, 31, 3–122, 2007.

[R1087]

(1, 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

Examples

Generate an Erdős–Rényi random graph G(n,c/n), with kernel kappa(x,y)=c where c is the mean expected degree.

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