random_kernel_graph¶
-
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 kernelkappa(x,y)
[1]. The kernelkappa(x,y)
must be a symmetric (inx,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 equationF(y,a,b) = r
. If None, the root is found usingscipy.optimize.brentq()
(this requires SciPy). - seed (int, optional) – Seed for random number generator (default=None)
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 timeO(n+m)
where m is the expected number of edges [2].The nodes are set to integers from 0 to n-1.
Examples
Generate an Erdős–Rényi random graph
G(n,c/n)
, with kernelkappa(x,y)=c
wherec
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)
See also
gnp_random_graph()
,expected_degree_graph()
References
[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