Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Generators for random graphs.
4"""
6import itertools
7import math
8from collections import defaultdict
10import networkx as nx
11from networkx.utils import py_random_state
13from ..utils.misc import check_create_using
14from .classic import complete_graph, empty_graph, path_graph, star_graph
15from .degree_seq import degree_sequence_tree
17__all__ = [
18 "fast_gnp_random_graph",
19 "gnp_random_graph",
20 "dense_gnm_random_graph",
21 "gnm_random_graph",
22 "erdos_renyi_graph",
23 "binomial_graph",
24 "newman_watts_strogatz_graph",
25 "watts_strogatz_graph",
26 "connected_watts_strogatz_graph",
27 "random_regular_graph",
28 "barabasi_albert_graph",
29 "dual_barabasi_albert_graph",
30 "extended_barabasi_albert_graph",
31 "powerlaw_cluster_graph",
32 "random_lobster",
33 "random_lobster_graph",
34 "random_shell_graph",
35 "random_powerlaw_tree",
36 "random_powerlaw_tree_sequence",
37 "random_kernel_graph",
38]
41@py_random_state(2)
42@nx._dispatchable(graphs=None, returns_graph=True)
43def fast_gnp_random_graph(n, p, seed=None, directed=False, *, create_using=None):
44 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph or
45 a binomial graph.
47 Parameters
48 ----------
49 n : int
50 The number of nodes.
51 p : float
52 Probability for edge creation.
53 seed : integer, random_state, or None (default)
54 Indicator of random number generation state.
55 See :ref:`Randomness<randomness>`.
56 directed : bool, optional (default=False)
57 If True, this function returns a directed graph.
58 create_using : Graph constructor, optional (default=nx.Graph or nx.DiGraph)
59 Graph type to create. If graph instance, then cleared before populated.
60 Multigraph types are not supported and raise a ``NetworkXError``.
61 By default NetworkX Graph or DiGraph are used depending on `directed`.
63 Notes
64 -----
65 The $G_{n,p}$ graph algorithm chooses each of the $[n (n - 1)] / 2$
66 (undirected) or $n (n - 1)$ (directed) possible edges with probability $p$.
68 This algorithm [1]_ runs in $O(n + m)$ time, where `m` is the expected number of
69 edges, which equals $p n (n - 1) / 2$. This should be faster than
70 :func:`gnp_random_graph` when $p$ is small and the expected number of edges
71 is small (that is, the graph is sparse).
73 See Also
74 --------
75 gnp_random_graph
77 References
78 ----------
79 .. [1] Vladimir Batagelj and Ulrik Brandes,
80 "Efficient generation of large random networks",
81 Phys. Rev. E, 71, 036113, 2005.
82 """
83 default = nx.DiGraph if directed else nx.Graph
84 create_using = check_create_using(
85 create_using, directed=directed, multigraph=False, default=default
86 )
87 if p <= 0 or p >= 1:
88 return nx.gnp_random_graph(
89 n, p, seed=seed, directed=directed, create_using=create_using
90 )
92 G = empty_graph(n, create_using=create_using)
94 lp = math.log(1.0 - p)
96 if directed:
97 v = 1
98 w = -1
99 while v < n:
100 lr = math.log(1.0 - seed.random())
101 w = w + 1 + int(lr / lp)
102 while w >= v and v < n:
103 w = w - v
104 v = v + 1
105 if v < n:
106 G.add_edge(w, v)
108 # Nodes in graph are from 0,n-1 (start with v as the second node index).
109 v = 1
110 w = -1
111 while v < n:
112 lr = math.log(1.0 - seed.random())
113 w = w + 1 + int(lr / lp)
114 while w >= v and v < n:
115 w = w - v
116 v = v + 1
117 if v < n:
118 G.add_edge(v, w)
119 return G
122@py_random_state(2)
123@nx._dispatchable(graphs=None, returns_graph=True)
124def gnp_random_graph(n, p, seed=None, directed=False, *, create_using=None):
125 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph
126 or a binomial graph.
128 The $G_{n,p}$ model chooses each of the possible edges with probability $p$.
130 Parameters
131 ----------
132 n : int
133 The number of nodes.
134 p : float
135 Probability for edge creation.
136 seed : integer, random_state, or None (default)
137 Indicator of random number generation state.
138 See :ref:`Randomness<randomness>`.
139 directed : bool, optional (default=False)
140 If True, this function returns a directed graph.
141 create_using : Graph constructor, optional (default=nx.Graph or nx.DiGraph)
142 Graph type to create. If graph instance, then cleared before populated.
143 Multigraph types are not supported and raise a ``NetworkXError``.
144 By default NetworkX Graph or DiGraph are used depending on `directed`.
146 See Also
147 --------
148 fast_gnp_random_graph
150 Notes
151 -----
152 This algorithm [2]_ runs in $O(n^2)$ time. For sparse graphs (that is, for
153 small values of $p$), :func:`fast_gnp_random_graph` is a faster algorithm.
155 :func:`binomial_graph` and :func:`erdos_renyi_graph` are
156 aliases for :func:`gnp_random_graph`.
158 >>> nx.binomial_graph is nx.gnp_random_graph
159 True
160 >>> nx.erdos_renyi_graph is nx.gnp_random_graph
161 True
163 References
164 ----------
165 .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
166 .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
167 """
168 default = nx.DiGraph if directed else nx.Graph
169 create_using = check_create_using(
170 create_using, directed=directed, multigraph=False, default=default
171 )
172 if p >= 1:
173 return complete_graph(n, create_using=create_using)
175 G = nx.empty_graph(n, create_using=create_using)
176 if p <= 0:
177 return G
179 edgetool = itertools.permutations if directed else itertools.combinations
180 for e in edgetool(range(n), 2):
181 if seed.random() < p:
182 G.add_edge(*e)
183 return G
186# add some aliases to common names
187binomial_graph = gnp_random_graph
188erdos_renyi_graph = gnp_random_graph
191@py_random_state(2)
192@nx._dispatchable(graphs=None, returns_graph=True)
193def dense_gnm_random_graph(n, m, seed=None, *, create_using=None):
194 """Returns a $G_{n,m}$ random graph.
196 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
197 of all graphs with $n$ nodes and $m$ edges.
199 This algorithm should be faster than :func:`gnm_random_graph` for dense
200 graphs.
202 Parameters
203 ----------
204 n : int
205 The number of nodes.
206 m : int
207 The number of edges.
208 seed : integer, random_state, or None (default)
209 Indicator of random number generation state.
210 See :ref:`Randomness<randomness>`.
211 create_using : Graph constructor, optional (default=nx.Graph)
212 Graph type to create. If graph instance, then cleared before populated.
213 Multigraph and directed types are not supported and raise a ``NetworkXError``.
215 See Also
216 --------
217 gnm_random_graph
219 Notes
220 -----
221 Algorithm by Keith M. Briggs Mar 31, 2006.
222 Inspired by Knuth's Algorithm S (Selection sampling technique),
223 in section 3.4.2 of [1]_.
225 References
226 ----------
227 .. [1] Donald E. Knuth, The Art of Computer Programming,
228 Volume 2/Seminumerical algorithms, Third Edition, Addison-Wesley, 1997.
229 """
230 create_using = check_create_using(create_using, directed=False, multigraph=False)
231 mmax = n * (n - 1) // 2
232 if m >= mmax:
233 return complete_graph(n, create_using)
234 G = empty_graph(n, create_using)
236 if n == 1:
237 return G
239 u = 0
240 v = 1
241 t = 0
242 k = 0
243 while True:
244 if seed.randrange(mmax - t) < m - k:
245 G.add_edge(u, v)
246 k += 1
247 if k == m:
248 return G
249 t += 1
250 v += 1
251 if v == n: # go to next row of adjacency matrix
252 u += 1
253 v = u + 1
256@py_random_state(2)
257@nx._dispatchable(graphs=None, returns_graph=True)
258def gnm_random_graph(n, m, seed=None, directed=False, *, create_using=None):
259 """Returns a $G_{n,m}$ random graph.
261 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
262 of all graphs with $n$ nodes and $m$ edges.
264 This algorithm should be faster than :func:`dense_gnm_random_graph` for
265 sparse graphs.
267 Parameters
268 ----------
269 n : int
270 The number of nodes.
271 m : int
272 The number of edges.
273 seed : integer, random_state, or None (default)
274 Indicator of random number generation state.
275 See :ref:`Randomness<randomness>`.
276 directed : bool, optional (default=False)
277 If True return a directed graph
278 create_using : Graph constructor, optional (default=nx.Graph or nx.DiGraph)
279 Graph type to create. If graph instance, then cleared before populated.
280 Multigraph types are not supported and raise a ``NetworkXError``.
281 By default NetworkX Graph or DiGraph are used depending on `directed`.
283 See also
284 --------
285 dense_gnm_random_graph
287 """
288 default = nx.DiGraph if directed else nx.Graph
289 create_using = check_create_using(
290 create_using, directed=directed, multigraph=False, default=default
291 )
292 if n == 1:
293 return nx.empty_graph(n, create_using=create_using)
294 max_edges = n * (n - 1) if directed else n * (n - 1) / 2.0
295 if m >= max_edges:
296 return complete_graph(n, create_using=create_using)
298 G = nx.empty_graph(n, create_using=create_using)
299 nlist = list(G)
300 edge_count = 0
301 while edge_count < m:
302 # generate random edge,u,v
303 u = seed.choice(nlist)
304 v = seed.choice(nlist)
305 if u == v or G.has_edge(u, v):
306 continue
307 else:
308 G.add_edge(u, v)
309 edge_count = edge_count + 1
310 return G
313@py_random_state(3)
314@nx._dispatchable(graphs=None, returns_graph=True)
315def newman_watts_strogatz_graph(n, k, p, seed=None, *, create_using=None):
316 """Returns a Newman–Watts–Strogatz small-world graph.
318 Parameters
319 ----------
320 n : int
321 The number of nodes.
322 k : int
323 Each node is joined with its `k` nearest neighbors in a ring
324 topology.
325 p : float
326 The probability of adding a new edge for each edge.
327 seed : integer, random_state, or None (default)
328 Indicator of random number generation state.
329 See :ref:`Randomness<randomness>`.
330 create_using : Graph constructor, optional (default=nx.Graph)
331 Graph type to create. If graph instance, then cleared before populated.
332 Multigraph and directed types are not supported and raise a ``NetworkXError``.
334 Notes
335 -----
336 First create a ring over $n$ nodes [1]_. Then each node in the ring is
337 connected with its $k$ nearest neighbors (or $k - 1$ neighbors if $k$
338 is odd). Then shortcuts are created by adding new edges as follows: for
339 each edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest
340 neighbors" with probability $p$ add a new edge $(u, w)$ with
341 randomly-chosen existing node $w$. In contrast with
342 :func:`watts_strogatz_graph`, no edges are removed.
344 See Also
345 --------
346 watts_strogatz_graph
348 References
349 ----------
350 .. [1] M. E. J. Newman and D. J. Watts,
351 Renormalization group analysis of the small-world network model,
352 Physics Letters A, 263, 341, 1999.
353 https://doi.org/10.1016/S0375-9601(99)00757-4
354 """
355 create_using = check_create_using(create_using, directed=False, multigraph=False)
356 if k > n:
357 raise nx.NetworkXError("k>=n, choose smaller k or larger n")
359 # If k == n the graph return is a complete graph
360 if k == n:
361 return nx.complete_graph(n, create_using)
363 G = empty_graph(n, create_using)
364 nlist = list(G.nodes())
365 fromv = nlist
366 # connect the k/2 neighbors
367 for j in range(1, k // 2 + 1):
368 tov = fromv[j:] + fromv[0:j] # the first j are now last
369 for i in range(len(fromv)):
370 G.add_edge(fromv[i], tov[i])
371 # for each edge u-v, with probability p, randomly select existing
372 # node w and add new edge u-w
373 e = list(G.edges())
374 for u, v in e:
375 if seed.random() < p:
376 w = seed.choice(nlist)
377 # no self-loops and reject if edge u-w exists
378 # is that the correct NWS model?
379 while w == u or G.has_edge(u, w):
380 w = seed.choice(nlist)
381 if G.degree(u) >= n - 1:
382 break # skip this rewiring
383 else:
384 G.add_edge(u, w)
385 return G
388@py_random_state(3)
389@nx._dispatchable(graphs=None, returns_graph=True)
390def watts_strogatz_graph(n, k, p, seed=None, *, create_using=None):
391 """Returns a Watts–Strogatz small-world graph.
393 Parameters
394 ----------
395 n : int
396 The number of nodes
397 k : int
398 Each node is joined with its `k` nearest neighbors in a ring
399 topology.
400 p : float
401 The probability of rewiring each edge
402 seed : integer, random_state, or None (default)
403 Indicator of random number generation state.
404 See :ref:`Randomness<randomness>`.
405 create_using : Graph constructor, optional (default=nx.Graph)
406 Graph type to create. If graph instance, then cleared before populated.
407 Multigraph and directed types are not supported and raise a ``NetworkXError``.
409 See Also
410 --------
411 newman_watts_strogatz_graph
412 connected_watts_strogatz_graph
414 Notes
415 -----
416 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined
417 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
418 Then shortcuts are created by replacing some edges as follows: for each
419 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
420 with probability $p$ replace it with a new edge $(u, w)$ with uniformly
421 random choice of existing node $w$.
423 In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring
424 does not increase the number of edges. The rewired graph is not guaranteed
425 to be connected as in :func:`connected_watts_strogatz_graph`.
427 References
428 ----------
429 .. [1] Duncan J. Watts and Steven H. Strogatz,
430 Collective dynamics of small-world networks,
431 Nature, 393, pp. 440--442, 1998.
432 """
433 create_using = check_create_using(create_using, directed=False, multigraph=False)
434 if k > n:
435 raise nx.NetworkXError("k>n, choose smaller k or larger n")
437 # If k == n, the graph is complete not Watts-Strogatz
438 if k == n:
439 G = nx.complete_graph(n, create_using)
440 return G
442 G = nx.empty_graph(n, create_using=create_using)
443 nodes = list(range(n)) # nodes are labeled 0 to n-1
444 # connect each node to k/2 neighbors
445 for j in range(1, k // 2 + 1):
446 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
447 G.add_edges_from(zip(nodes, targets))
448 # rewire edges from each node
449 # loop over all nodes in order (label) and neighbors in order (distance)
450 # no self loops or multiple edges allowed
451 for j in range(1, k // 2 + 1): # outer loop is neighbors
452 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
453 # inner loop in node order
454 for u, v in zip(nodes, targets):
455 if seed.random() < p:
456 w = seed.choice(nodes)
457 # Enforce no self-loops or multiple edges
458 while w == u or G.has_edge(u, w):
459 w = seed.choice(nodes)
460 if G.degree(u) >= n - 1:
461 break # skip this rewiring
462 else:
463 G.remove_edge(u, v)
464 G.add_edge(u, w)
465 return G
468@py_random_state(4)
469@nx._dispatchable(graphs=None, returns_graph=True)
470def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None, *, create_using=None):
471 """Returns a connected Watts–Strogatz small-world graph.
473 Attempts to generate a connected graph by repeated generation of
474 Watts–Strogatz small-world graphs. An exception is raised if the maximum
475 number of tries is exceeded.
477 Parameters
478 ----------
479 n : int
480 The number of nodes
481 k : int
482 Each node is joined with its `k` nearest neighbors in a ring
483 topology.
484 p : float
485 The probability of rewiring each edge
486 tries : int
487 Number of attempts to generate a connected graph.
488 seed : integer, random_state, or None (default)
489 Indicator of random number generation state.
490 See :ref:`Randomness<randomness>`.
491 create_using : Graph constructor, optional (default=nx.Graph)
492 Graph type to create. If graph instance, then cleared before populated.
493 Multigraph and directed types are not supported and raise a ``NetworkXError``.
495 Notes
496 -----
497 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined
498 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
499 Then shortcuts are created by replacing some edges as follows: for each
500 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
501 with probability $p$ replace it with a new edge $(u, w)$ with uniformly
502 random choice of existing node $w$.
503 The entire process is repeated until a connected graph results.
505 See Also
506 --------
507 newman_watts_strogatz_graph
508 watts_strogatz_graph
510 References
511 ----------
512 .. [1] Duncan J. Watts and Steven H. Strogatz,
513 Collective dynamics of small-world networks,
514 Nature, 393, pp. 440--442, 1998.
515 """
516 for i in range(tries):
517 # seed is an RNG so should change sequence each call
518 G = watts_strogatz_graph(n, k, p, seed, create_using=create_using)
519 if nx.is_connected(G):
520 return G
521 raise nx.NetworkXError("Maximum number of tries exceeded")
524@py_random_state(2)
525@nx._dispatchable(graphs=None, returns_graph=True)
526def random_regular_graph(d, n, seed=None, *, create_using=None):
527 r"""Returns a random $d$-regular graph on $n$ nodes.
529 A regular graph is a graph where each node has the same number of neighbors.
531 The resulting graph has no self-loops or parallel edges.
533 Parameters
534 ----------
535 d : int
536 The degree of each node.
537 n : integer
538 The number of nodes. The value of $n \times d$ must be even.
539 seed : integer, random_state, or None (default)
540 Indicator of random number generation state.
541 See :ref:`Randomness<randomness>`.
542 create_using : Graph constructor, optional (default=nx.Graph)
543 Graph type to create. If graph instance, then cleared before populated.
544 Multigraph and directed types are not supported and raise a ``NetworkXError``.
546 Notes
547 -----
548 The nodes are numbered from $0$ to $n - 1$.
550 Kim and Vu's paper [2]_ shows that this algorithm samples in an
551 asymptotically uniform way from the space of random graphs when
552 $d = O(n^{1 / 3 - \epsilon})$.
554 Raises
555 ------
557 NetworkXError
558 If $n \times d$ is odd or $d$ is greater than or equal to $n$.
560 References
561 ----------
562 .. [1] A. Steger and N. Wormald,
563 Generating random regular graphs quickly,
564 Probability and Computing 8 (1999), 377-396, 1999.
565 https://doi.org/10.1017/S0963548399003867
567 .. [2] Jeong Han Kim and Van H. Vu,
568 Generating random regular graphs,
569 Proceedings of the thirty-fifth ACM symposium on Theory of computing,
570 San Diego, CA, USA, pp 213--222, 2003.
571 http://portal.acm.org/citation.cfm?id=780542.780576
572 """
573 create_using = check_create_using(create_using, directed=False, multigraph=False)
574 if (n * d) % 2 != 0:
575 raise nx.NetworkXError("n * d must be even")
577 if not 0 <= d < n:
578 raise nx.NetworkXError("the 0 <= d < n inequality must be satisfied")
580 G = nx.empty_graph(n, create_using=create_using)
582 if d == 0:
583 return G
585 def _suitable(edges, potential_edges):
586 # Helper subroutine to check if there are suitable edges remaining
587 # If False, the generation of the graph has failed
588 if not potential_edges:
589 return True
590 for s1 in potential_edges:
591 for s2 in potential_edges:
592 # Two iterators on the same dictionary are guaranteed
593 # to visit it in the same order if there are no
594 # intervening modifications.
595 if s1 == s2:
596 # Only need to consider s1-s2 pair one time
597 break
598 if s1 > s2:
599 s1, s2 = s2, s1
600 if (s1, s2) not in edges:
601 return True
602 return False
604 def _try_creation():
605 # Attempt to create an edge set
607 edges = set()
608 stubs = list(range(n)) * d
610 while stubs:
611 potential_edges = defaultdict(lambda: 0)
612 seed.shuffle(stubs)
613 stubiter = iter(stubs)
614 for s1, s2 in zip(stubiter, stubiter):
615 if s1 > s2:
616 s1, s2 = s2, s1
617 if s1 != s2 and ((s1, s2) not in edges):
618 edges.add((s1, s2))
619 else:
620 potential_edges[s1] += 1
621 potential_edges[s2] += 1
623 if not _suitable(edges, potential_edges):
624 return None # failed to find suitable edge set
626 stubs = [
627 node
628 for node, potential in potential_edges.items()
629 for _ in range(potential)
630 ]
631 return edges
633 # Even though a suitable edge set exists,
634 # the generation of such a set is not guaranteed.
635 # Try repeatedly to find one.
636 edges = _try_creation()
637 while edges is None:
638 edges = _try_creation()
639 G.add_edges_from(edges)
641 return G
644def _random_subset(seq, m, rng):
645 """Return m unique elements from seq.
647 This differs from random.sample which can return repeated
648 elements if seq holds repeated elements.
650 Note: rng is a random.Random or numpy.random.RandomState instance.
651 """
652 targets = set()
653 while len(targets) < m:
654 x = rng.choice(seq)
655 targets.add(x)
656 return targets
659@py_random_state(2)
660@nx._dispatchable(graphs=None, returns_graph=True)
661def barabasi_albert_graph(n, m, seed=None, initial_graph=None, *, create_using=None):
662 """Returns a random graph using Barabási–Albert preferential attachment
664 A graph of $n$ nodes is grown by attaching new nodes each with $m$
665 edges that are preferentially attached to existing nodes with high degree.
667 Parameters
668 ----------
669 n : int
670 Number of nodes
671 m : int
672 Number of edges to attach from a new node to existing nodes
673 seed : integer, random_state, or None (default)
674 Indicator of random number generation state.
675 See :ref:`Randomness<randomness>`.
676 initial_graph : Graph or None (default)
677 Initial network for Barabási–Albert algorithm.
678 It should be a connected graph for most use cases.
679 A copy of `initial_graph` is used.
680 If None, starts from a star graph on (m+1) nodes.
681 create_using : Graph constructor, optional (default=nx.Graph)
682 Graph type to create. If graph instance, then cleared before populated.
683 Multigraph and directed types are not supported and raise a ``NetworkXError``.
685 Returns
686 -------
687 G : Graph
689 Raises
690 ------
691 NetworkXError
692 If `m` does not satisfy ``1 <= m < n``, or
693 the initial graph number of nodes m0 does not satisfy ``m <= m0 <= n``.
695 References
696 ----------
697 .. [1] A. L. Barabási and R. Albert "Emergence of scaling in
698 random networks", Science 286, pp 509-512, 1999.
699 """
700 create_using = check_create_using(create_using, directed=False, multigraph=False)
701 if m < 1 or m >= n:
702 raise nx.NetworkXError(
703 f"Barabási–Albert network must have m >= 1 and m < n, m = {m}, n = {n}"
704 )
706 if initial_graph is None:
707 # Default initial graph : star graph on (m + 1) nodes
708 G = star_graph(m, create_using)
709 else:
710 if len(initial_graph) < m or len(initial_graph) > n:
711 raise nx.NetworkXError(
712 f"Barabási–Albert initial graph needs between m={m} and n={n} nodes"
713 )
714 G = initial_graph.copy()
716 # List of existing nodes, with nodes repeated once for each adjacent edge
717 repeated_nodes = [n for n, d in G.degree() for _ in range(d)]
718 # Start adding the other n - m0 nodes.
719 source = len(G)
720 while source < n:
721 # Now choose m unique nodes from the existing nodes
722 # Pick uniformly from repeated_nodes (preferential attachment)
723 targets = _random_subset(repeated_nodes, m, seed)
724 # Add edges to m nodes from the source.
725 G.add_edges_from(zip([source] * m, targets))
726 # Add one node to the list for each new edge just created.
727 repeated_nodes.extend(targets)
728 # And the new node "source" has m edges to add to the list.
729 repeated_nodes.extend([source] * m)
731 source += 1
732 return G
735@py_random_state(4)
736@nx._dispatchable(graphs=None, returns_graph=True)
737def dual_barabasi_albert_graph(
738 n, m1, m2, p, seed=None, initial_graph=None, *, create_using=None
739):
740 """Returns a random graph using dual Barabási–Albert preferential attachment
742 A graph of $n$ nodes is grown by attaching new nodes each with either $m_1$
743 edges (with probability $p$) or $m_2$ edges (with probability $1-p$) that
744 are preferentially attached to existing nodes with high degree.
746 Parameters
747 ----------
748 n : int
749 Number of nodes
750 m1 : int
751 Number of edges to link each new node to existing nodes with probability $p$
752 m2 : int
753 Number of edges to link each new node to existing nodes with probability $1-p$
754 p : float
755 The probability of attaching $m_1$ edges (as opposed to $m_2$ edges)
756 seed : integer, random_state, or None (default)
757 Indicator of random number generation state.
758 See :ref:`Randomness<randomness>`.
759 initial_graph : Graph or None (default)
760 Initial network for Barabási–Albert algorithm.
761 A copy of `initial_graph` is used.
762 It should be connected for most use cases.
763 If None, starts from an star graph on max(m1, m2) + 1 nodes.
764 create_using : Graph constructor, optional (default=nx.Graph)
765 Graph type to create. If graph instance, then cleared before populated.
766 Multigraph and directed types are not supported and raise a ``NetworkXError``.
768 Returns
769 -------
770 G : Graph
772 Raises
773 ------
774 NetworkXError
775 If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n``, or
776 `p` does not satisfy ``0 <= p <= 1``, or
777 the initial graph number of nodes m0 does not satisfy m1, m2 <= m0 <= n.
779 References
780 ----------
781 .. [1] N. Moshiri "The dual-Barabasi-Albert model", arXiv:1810.10538.
782 """
783 create_using = check_create_using(create_using, directed=False, multigraph=False)
784 if m1 < 1 or m1 >= n:
785 raise nx.NetworkXError(
786 f"Dual Barabási–Albert must have m1 >= 1 and m1 < n, m1 = {m1}, n = {n}"
787 )
788 if m2 < 1 or m2 >= n:
789 raise nx.NetworkXError(
790 f"Dual Barabási–Albert must have m2 >= 1 and m2 < n, m2 = {m2}, n = {n}"
791 )
792 if p < 0 or p > 1:
793 raise nx.NetworkXError(
794 f"Dual Barabási–Albert network must have 0 <= p <= 1, p = {p}"
795 )
797 # For simplicity, if p == 0 or 1, just return BA
798 if p == 1:
799 return barabasi_albert_graph(n, m1, seed, create_using=create_using)
800 elif p == 0:
801 return barabasi_albert_graph(n, m2, seed, create_using=create_using)
803 if initial_graph is None:
804 # Default initial graph : star graph on max(m1, m2) nodes
805 G = star_graph(max(m1, m2), create_using)
806 else:
807 if len(initial_graph) < max(m1, m2) or len(initial_graph) > n:
808 raise nx.NetworkXError(
809 f"Barabási–Albert initial graph must have between "
810 f"max(m1, m2) = {max(m1, m2)} and n = {n} nodes"
811 )
812 G = initial_graph.copy()
814 # Target nodes for new edges
815 targets = list(G)
816 # List of existing nodes, with nodes repeated once for each adjacent edge
817 repeated_nodes = [n for n, d in G.degree() for _ in range(d)]
818 # Start adding the remaining nodes.
819 source = len(G)
820 while source < n:
821 # Pick which m to use (m1 or m2)
822 if seed.random() < p:
823 m = m1
824 else:
825 m = m2
826 # Now choose m unique nodes from the existing nodes
827 # Pick uniformly from repeated_nodes (preferential attachment)
828 targets = _random_subset(repeated_nodes, m, seed)
829 # Add edges to m nodes from the source.
830 G.add_edges_from(zip([source] * m, targets))
831 # Add one node to the list for each new edge just created.
832 repeated_nodes.extend(targets)
833 # And the new node "source" has m edges to add to the list.
834 repeated_nodes.extend([source] * m)
836 source += 1
837 return G
840@py_random_state(4)
841@nx._dispatchable(graphs=None, returns_graph=True)
842def extended_barabasi_albert_graph(n, m, p, q, seed=None, *, create_using=None):
843 """Returns an extended Barabási–Albert model graph.
845 An extended Barabási–Albert model graph is a random graph constructed
846 using preferential attachment. The extended model allows new edges,
847 rewired edges or new nodes. Based on the probabilities $p$ and $q$
848 with $p + q < 1$, the growing behavior of the graph is determined as:
850 1) With $p$ probability, $m$ new edges are added to the graph,
851 starting from randomly chosen existing nodes and attached preferentially at the
852 other end.
854 2) With $q$ probability, $m$ existing edges are rewired
855 by randomly choosing an edge and rewiring one end to a preferentially chosen node.
857 3) With $(1 - p - q)$ probability, $m$ new nodes are added to the graph
858 with edges attached preferentially.
860 When $p = q = 0$, the model behaves just like the Barabási–Alber model.
862 Parameters
863 ----------
864 n : int
865 Number of nodes
866 m : int
867 Number of edges with which a new node attaches to existing nodes
868 p : float
869 Probability value for adding an edge between existing nodes. p + q < 1
870 q : float
871 Probability value of rewiring of existing edges. p + q < 1
872 seed : integer, random_state, or None (default)
873 Indicator of random number generation state.
874 See :ref:`Randomness<randomness>`.
875 create_using : Graph constructor, optional (default=nx.Graph)
876 Graph type to create. If graph instance, then cleared before populated.
877 Multigraph and directed types are not supported and raise a ``NetworkXError``.
879 Returns
880 -------
881 G : Graph
883 Raises
884 ------
885 NetworkXError
886 If `m` does not satisfy ``1 <= m < n`` or ``1 >= p + q``
888 References
889 ----------
890 .. [1] Albert, R., & Barabási, A. L. (2000)
891 Topology of evolving networks: local events and universality
892 Physical review letters, 85(24), 5234.
893 """
894 create_using = check_create_using(create_using, directed=False, multigraph=False)
895 if m < 1 or m >= n:
896 msg = f"Extended Barabasi-Albert network needs m>=1 and m<n, m={m}, n={n}"
897 raise nx.NetworkXError(msg)
898 if p + q >= 1:
899 msg = f"Extended Barabasi-Albert network needs p + q <= 1, p={p}, q={q}"
900 raise nx.NetworkXError(msg)
902 # Add m initial nodes (m0 in barabasi-speak)
903 G = empty_graph(m, create_using)
905 # List of nodes to represent the preferential attachment random selection.
906 # At the creation of the graph, all nodes are added to the list
907 # so that even nodes that are not connected have a chance to get selected,
908 # for rewiring and adding of edges.
909 # With each new edge, nodes at the ends of the edge are added to the list.
910 attachment_preference = []
911 attachment_preference.extend(range(m))
913 # Start adding the other n-m nodes. The first node is m.
914 new_node = m
915 while new_node < n:
916 a_probability = seed.random()
918 # Total number of edges of a Clique of all the nodes
919 clique_degree = len(G) - 1
920 clique_size = (len(G) * clique_degree) / 2
922 # Adding m new edges, if there is room to add them
923 if a_probability < p and G.size() <= clique_size - m:
924 # Select the nodes where an edge can be added
925 eligible_nodes = [nd for nd, deg in G.degree() if deg < clique_degree]
926 for i in range(m):
927 # Choosing a random source node from eligible_nodes
928 src_node = seed.choice(eligible_nodes)
930 # Picking a possible node that is not 'src_node' or
931 # neighbor with 'src_node', with preferential attachment
932 prohibited_nodes = list(G[src_node])
933 prohibited_nodes.append(src_node)
934 # This will raise an exception if the sequence is empty
935 dest_node = seed.choice(
936 [nd for nd in attachment_preference if nd not in prohibited_nodes]
937 )
938 # Adding the new edge
939 G.add_edge(src_node, dest_node)
941 # Appending both nodes to add to their preferential attachment
942 attachment_preference.append(src_node)
943 attachment_preference.append(dest_node)
945 # Adjusting the eligible nodes. Degree may be saturated.
946 if G.degree(src_node) == clique_degree:
947 eligible_nodes.remove(src_node)
948 if G.degree(dest_node) == clique_degree and dest_node in eligible_nodes:
949 eligible_nodes.remove(dest_node)
951 # Rewiring m edges, if there are enough edges
952 elif p <= a_probability < (p + q) and m <= G.size() < clique_size:
953 # Selecting nodes that have at least 1 edge but that are not
954 # fully connected to ALL other nodes (center of star).
955 # These nodes are the pivot nodes of the edges to rewire
956 eligible_nodes = [nd for nd, deg in G.degree() if 0 < deg < clique_degree]
957 for i in range(m):
958 # Choosing a random source node
959 node = seed.choice(eligible_nodes)
961 # The available nodes do have a neighbor at least.
962 nbr_nodes = list(G[node])
964 # Choosing the other end that will get detached
965 src_node = seed.choice(nbr_nodes)
967 # Picking a target node that is not 'node' or
968 # neighbor with 'node', with preferential attachment
969 nbr_nodes.append(node)
970 dest_node = seed.choice(
971 [nd for nd in attachment_preference if nd not in nbr_nodes]
972 )
973 # Rewire
974 G.remove_edge(node, src_node)
975 G.add_edge(node, dest_node)
977 # Adjusting the preferential attachment list
978 attachment_preference.remove(src_node)
979 attachment_preference.append(dest_node)
981 # Adjusting the eligible nodes.
982 # nodes may be saturated or isolated.
983 if G.degree(src_node) == 0 and src_node in eligible_nodes:
984 eligible_nodes.remove(src_node)
985 if dest_node in eligible_nodes:
986 if G.degree(dest_node) == clique_degree:
987 eligible_nodes.remove(dest_node)
988 else:
989 if G.degree(dest_node) == 1:
990 eligible_nodes.append(dest_node)
992 # Adding new node with m edges
993 else:
994 # Select the edges' nodes by preferential attachment
995 targets = _random_subset(attachment_preference, m, seed)
996 G.add_edges_from(zip([new_node] * m, targets))
998 # Add one node to the list for each new edge just created.
999 attachment_preference.extend(targets)
1000 # The new node has m edges to it, plus itself: m + 1
1001 attachment_preference.extend([new_node] * (m + 1))
1002 new_node += 1
1003 return G
1006@py_random_state(3)
1007@nx._dispatchable(graphs=None, returns_graph=True)
1008def powerlaw_cluster_graph(n, m, p, seed=None, *, create_using=None):
1009 """Holme and Kim algorithm for growing graphs with powerlaw
1010 degree distribution and approximate average clustering.
1012 Parameters
1013 ----------
1014 n : int
1015 the number of nodes
1016 m : int
1017 the number of random edges to add for each new node
1018 p : float,
1019 Probability of adding a triangle after adding a random edge
1020 seed : integer, random_state, or None (default)
1021 Indicator of random number generation state.
1022 See :ref:`Randomness<randomness>`.
1023 create_using : Graph constructor, optional (default=nx.Graph)
1024 Graph type to create. If graph instance, then cleared before populated.
1025 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1027 Notes
1028 -----
1029 The average clustering has a hard time getting above a certain
1030 cutoff that depends on `m`. This cutoff is often quite low. The
1031 transitivity (fraction of triangles to possible triangles) seems to
1032 decrease with network size.
1034 It is essentially the Barabási–Albert (BA) growth model with an
1035 extra step that each random edge is followed by a chance of
1036 making an edge to one of its neighbors too (and thus a triangle).
1038 This algorithm improves on BA in the sense that it enables a
1039 higher average clustering to be attained if desired.
1041 It seems possible to have a disconnected graph with this algorithm
1042 since the initial `m` nodes may not be all linked to a new node
1043 on the first iteration like the BA model.
1045 Raises
1046 ------
1047 NetworkXError
1048 If `m` does not satisfy ``1 <= m <= n`` or `p` does not
1049 satisfy ``0 <= p <= 1``.
1051 References
1052 ----------
1053 .. [1] P. Holme and B. J. Kim,
1054 "Growing scale-free networks with tunable clustering",
1055 Phys. Rev. E, 65, 026107, 2002.
1056 """
1057 create_using = check_create_using(create_using, directed=False, multigraph=False)
1058 if m < 1 or n < m:
1059 raise nx.NetworkXError(f"NetworkXError must have m>1 and m<n, m={m},n={n}")
1061 if p > 1 or p < 0:
1062 raise nx.NetworkXError(f"NetworkXError p must be in [0,1], p={p}")
1064 G = empty_graph(m, create_using) # add m initial nodes (m0 in barabasi-speak)
1065 repeated_nodes = list(G) # list of existing nodes to sample from
1066 # with nodes repeated once for each adjacent edge
1067 source = m # next node is m
1068 while source < n: # Now add the other n-1 nodes
1069 possible_targets = _random_subset(repeated_nodes, m, seed)
1070 # do one preferential attachment for new node
1071 target = possible_targets.pop()
1072 G.add_edge(source, target)
1073 repeated_nodes.append(target) # add one node to list for each new link
1074 count = 1
1075 while count < m: # add m-1 more new links
1076 if seed.random() < p: # clustering step: add triangle
1077 neighborhood = [
1078 nbr
1079 for nbr in G.neighbors(target)
1080 if not G.has_edge(source, nbr) and nbr != source
1081 ]
1082 if neighborhood: # if there is a neighbor without a link
1083 nbr = seed.choice(neighborhood)
1084 G.add_edge(source, nbr) # add triangle
1085 repeated_nodes.append(nbr)
1086 count = count + 1
1087 continue # go to top of while loop
1088 # else do preferential attachment step if above fails
1089 target = possible_targets.pop()
1090 G.add_edge(source, target)
1091 repeated_nodes.append(target)
1092 count = count + 1
1094 repeated_nodes.extend([source] * m) # add source node to list m times
1095 source += 1
1096 return G
1099@py_random_state(3)
1100@nx._dispatchable(graphs=None, returns_graph=True)
1101def random_lobster_graph(n, p1, p2, seed=None, *, create_using=None):
1102 """Returns a random lobster graph.
1104 A lobster is a tree that reduces to a caterpillar when pruning all
1105 leaf nodes. A caterpillar is a tree that reduces to a path graph
1106 when pruning all leaf nodes; setting `p2` to zero produces a caterpillar.
1108 This implementation iterates on the probabilities `p1` and `p2` to add
1109 edges at levels 1 and 2, respectively. Graphs are therefore constructed
1110 iteratively with uniform randomness at each level rather than being selected
1111 uniformly at random from the set of all possible lobsters.
1113 Parameters
1114 ----------
1115 n : int
1116 The expected number of nodes in the backbone
1117 p1 : float
1118 Probability of adding an edge to the backbone
1119 p2 : float
1120 Probability of adding an edge one level beyond backbone
1121 seed : integer, random_state, or None (default)
1122 Indicator of random number generation state.
1123 See :ref:`Randomness<randomness>`.
1124 create_using : Graph constructor, optional (default=nx.Graph)
1125 Graph type to create. If graph instance, then cleared before populated.
1126 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1128 Raises
1129 ------
1130 NetworkXError
1131 If `p1` or `p2` parameters are >= 1 because the while loops would never finish.
1132 """
1133 create_using = check_create_using(create_using, directed=False, multigraph=False)
1134 p1, p2 = abs(p1), abs(p2)
1135 if any(p >= 1 for p in [p1, p2]):
1136 raise nx.NetworkXError("Probability values for `p1` and `p2` must both be < 1.")
1138 # a necessary ingredient in any self-respecting graph library
1139 llen = int(2 * seed.random() * n + 0.5)
1140 L = path_graph(llen, create_using)
1141 # build caterpillar: add edges to path graph with probability p1
1142 current_node = llen - 1
1143 for n in range(llen):
1144 while seed.random() < p1: # add fuzzy caterpillar parts
1145 current_node += 1
1146 L.add_edge(n, current_node)
1147 cat_node = current_node
1148 while seed.random() < p2: # add crunchy lobster bits
1149 current_node += 1
1150 L.add_edge(cat_node, current_node)
1151 return L # voila, un lobster!
1154@py_random_state(3)
1155@nx._dispatchable(graphs=None, returns_graph=True)
1156def random_lobster(n, p1, p2, seed=None, *, create_using=None):
1157 """
1158 .. deprecated:: 3.5
1159 `random_lobster` is a deprecated alias
1160 for `random_lobster_graph`.
1161 Use `random_lobster_graph` instead.
1162 """
1163 import warnings
1165 warnings.warn(
1166 "`random_lobster` is deprecated, use `random_lobster_graph` instead.",
1167 category=DeprecationWarning,
1168 stacklevel=2,
1169 )
1170 return random_lobster_graph(n, p1, p2, seed=seed, create_using=create_using)
1173@py_random_state(1)
1174@nx._dispatchable(graphs=None, returns_graph=True)
1175def random_shell_graph(constructor, seed=None, *, create_using=None):
1176 """Returns a random shell graph for the constructor given.
1178 Parameters
1179 ----------
1180 constructor : list of three-tuples
1181 Represents the parameters for a shell, starting at the center
1182 shell. Each element of the list must be of the form `(n, m,
1183 d)`, where `n` is the number of nodes in the shell, `m` is
1184 the number of edges in the shell, and `d` is the ratio of
1185 inter-shell (next) edges to intra-shell edges. If `d` is zero,
1186 there will be no intra-shell edges, and if `d` is one there
1187 will be all possible intra-shell edges.
1188 seed : integer, random_state, or None (default)
1189 Indicator of random number generation state.
1190 See :ref:`Randomness<randomness>`.
1191 create_using : Graph constructor, optional (default=nx.Graph)
1192 Graph type to create. Graph instances are not supported.
1193 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1195 Examples
1196 --------
1197 >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)]
1198 >>> G = nx.random_shell_graph(constructor)
1200 """
1201 create_using = check_create_using(create_using, directed=False, multigraph=False)
1202 G = empty_graph(0, create_using)
1204 glist = []
1205 intra_edges = []
1206 nnodes = 0
1207 # create gnm graphs for each shell
1208 for n, m, d in constructor:
1209 inter_edges = int(m * d)
1210 intra_edges.append(m - inter_edges)
1211 g = nx.convert_node_labels_to_integers(
1212 gnm_random_graph(n, inter_edges, seed=seed, create_using=G.__class__),
1213 first_label=nnodes,
1214 )
1215 glist.append(g)
1216 nnodes += n
1217 G = nx.operators.union(G, g)
1219 # connect the shells randomly
1220 for gi in range(len(glist) - 1):
1221 nlist1 = list(glist[gi])
1222 nlist2 = list(glist[gi + 1])
1223 total_edges = intra_edges[gi]
1224 edge_count = 0
1225 while edge_count < total_edges:
1226 u = seed.choice(nlist1)
1227 v = seed.choice(nlist2)
1228 if u == v or G.has_edge(u, v):
1229 continue
1230 else:
1231 G.add_edge(u, v)
1232 edge_count = edge_count + 1
1233 return G
1236@py_random_state(2)
1237@nx._dispatchable(graphs=None, returns_graph=True)
1238def random_powerlaw_tree(n, gamma=3, seed=None, tries=100, *, create_using=None):
1239 """Returns a tree with a power law degree distribution.
1241 Parameters
1242 ----------
1243 n : int
1244 The number of nodes.
1245 gamma : float
1246 Exponent of the power law.
1247 seed : integer, random_state, or None (default)
1248 Indicator of random number generation state.
1249 See :ref:`Randomness<randomness>`.
1250 tries : int
1251 Number of attempts to adjust the sequence to make it a tree.
1252 create_using : Graph constructor, optional (default=nx.Graph)
1253 Graph type to create. If graph instance, then cleared before populated.
1254 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1256 Raises
1257 ------
1258 NetworkXError
1259 If no valid sequence is found within the maximum number of
1260 attempts.
1262 Notes
1263 -----
1264 A trial power law degree sequence is chosen and then elements are
1265 swapped with new elements from a powerlaw distribution until the
1266 sequence makes a tree (by checking, for example, that the number of
1267 edges is one smaller than the number of nodes).
1269 """
1270 create_using = check_create_using(create_using, directed=False, multigraph=False)
1271 # This call may raise a NetworkXError if the number of tries is succeeded.
1272 seq = random_powerlaw_tree_sequence(n, gamma=gamma, seed=seed, tries=tries)
1273 G = degree_sequence_tree(seq, create_using)
1274 return G
1277@py_random_state(2)
1278@nx._dispatchable(graphs=None)
1279def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100):
1280 """Returns a degree sequence for a tree with a power law distribution.
1282 Parameters
1283 ----------
1284 n : int,
1285 The number of nodes.
1286 gamma : float
1287 Exponent of the power law.
1288 seed : integer, random_state, or None (default)
1289 Indicator of random number generation state.
1290 See :ref:`Randomness<randomness>`.
1291 tries : int
1292 Number of attempts to adjust the sequence to make it a tree.
1294 Raises
1295 ------
1296 NetworkXError
1297 If no valid sequence is found within the maximum number of
1298 attempts.
1300 Notes
1301 -----
1302 A trial power law degree sequence is chosen and then elements are
1303 swapped with new elements from a power law distribution until
1304 the sequence makes a tree (by checking, for example, that the number of
1305 edges is one smaller than the number of nodes).
1307 """
1308 # get trial sequence
1309 z = nx.utils.powerlaw_sequence(n, exponent=gamma, seed=seed)
1310 # round to integer values in the range [0,n]
1311 zseq = [min(n, max(round(s), 0)) for s in z]
1313 # another sequence to swap values from
1314 z = nx.utils.powerlaw_sequence(tries, exponent=gamma, seed=seed)
1315 # round to integer values in the range [0,n]
1316 swap = [min(n, max(round(s), 0)) for s in z]
1318 for _ in swap:
1319 valid, _ = nx.utils.is_valid_tree_degree_sequence(zseq)
1320 if valid:
1321 return zseq
1322 index = seed.randint(0, n - 1)
1323 zseq[index] = swap.pop()
1325 raise nx.NetworkXError(
1326 f"Exceeded max ({tries}) attempts for a valid tree sequence."
1327 )
1330@py_random_state(3)
1331@nx._dispatchable(graphs=None, returns_graph=True)
1332def random_kernel_graph(
1333 n, kernel_integral, kernel_root=None, seed=None, *, create_using=None
1334):
1335 r"""Returns an random graph based on the specified kernel.
1337 The algorithm chooses each of the $[n(n-1)]/2$ possible edges with
1338 probability specified by a kernel $\kappa(x,y)$ [1]_. The kernel
1339 $\kappa(x,y)$ must be a symmetric (in $x,y$), non-negative,
1340 bounded function.
1342 Parameters
1343 ----------
1344 n : int
1345 The number of nodes
1346 kernel_integral : function
1347 Function that returns the definite integral of the kernel $\kappa(x,y)$,
1348 $F(y,a,b) := \int_a^b \kappa(x,y)dx$
1349 kernel_root: function (optional)
1350 Function that returns the root $b$ of the equation $F(y,a,b) = r$.
1351 If None, the root is found using :func:`scipy.optimize.brentq`
1352 (this requires SciPy).
1353 seed : integer, random_state, or None (default)
1354 Indicator of random number generation state.
1355 See :ref:`Randomness<randomness>`.
1356 create_using : Graph constructor, optional (default=nx.Graph)
1357 Graph type to create. If graph instance, then cleared before populated.
1358 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1360 Notes
1361 -----
1362 The kernel is specified through its definite integral which must be
1363 provided as one of the arguments. If the integral and root of the
1364 kernel integral can be found in $O(1)$ time then this algorithm runs in
1365 time $O(n+m)$ where m is the expected number of edges [2]_.
1367 The nodes are set to integers from $0$ to $n-1$.
1369 Examples
1370 --------
1371 Generate an Erdős–Rényi random graph $G(n,c/n)$, with kernel
1372 $\kappa(x,y)=c$ where $c$ is the mean expected degree.
1374 >>> def integral(u, w, z):
1375 ... return c * (z - w)
1376 >>> def root(u, w, r):
1377 ... return r / c + w
1378 >>> c = 1
1379 >>> graph = nx.random_kernel_graph(1000, integral, root)
1381 See Also
1382 --------
1383 gnp_random_graph
1384 expected_degree_graph
1386 References
1387 ----------
1388 .. [1] Bollobás, Béla, Janson, S. and Riordan, O.
1389 "The phase transition in inhomogeneous random graphs",
1390 *Random Structures Algorithms*, 31, 3--122, 2007.
1392 .. [2] Hagberg A, Lemons N (2015),
1393 "Fast Generation of Sparse Random Kernel Graphs".
1394 PLoS ONE 10(9): e0135177, 2015. doi:10.1371/journal.pone.0135177
1395 """
1396 create_using = check_create_using(create_using, directed=False, multigraph=False)
1397 if kernel_root is None:
1398 import scipy as sp
1400 def kernel_root(y, a, r):
1401 def my_function(b):
1402 return kernel_integral(y, a, b) - r
1404 return sp.optimize.brentq(my_function, a, 1)
1406 graph = nx.empty_graph(create_using=create_using)
1407 graph.add_nodes_from(range(n))
1408 (i, j) = (1, 1)
1409 while i < n:
1410 r = -math.log(1 - seed.random()) # (1-seed.random()) in (0, 1]
1411 if kernel_integral(i / n, j / n, 1) <= r:
1412 i, j = i + 1, i + 1
1413 else:
1414 j = math.ceil(n * kernel_root(i / n, j / n, r))
1415 graph.add_edge(i - 1, j - 1)
1416 return graph