Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/random_graphs.py: 14%
432 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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 .classic import complete_graph, empty_graph, path_graph, star_graph
14from .degree_seq import degree_sequence_tree
16__all__ = [
17 "fast_gnp_random_graph",
18 "gnp_random_graph",
19 "dense_gnm_random_graph",
20 "gnm_random_graph",
21 "erdos_renyi_graph",
22 "binomial_graph",
23 "newman_watts_strogatz_graph",
24 "watts_strogatz_graph",
25 "connected_watts_strogatz_graph",
26 "random_regular_graph",
27 "barabasi_albert_graph",
28 "dual_barabasi_albert_graph",
29 "extended_barabasi_albert_graph",
30 "powerlaw_cluster_graph",
31 "random_lobster",
32 "random_shell_graph",
33 "random_powerlaw_tree",
34 "random_powerlaw_tree_sequence",
35 "random_kernel_graph",
36]
39@py_random_state(2)
40@nx._dispatch(graphs=None)
41def fast_gnp_random_graph(n, p, seed=None, directed=False):
42 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph or
43 a binomial graph.
45 Parameters
46 ----------
47 n : int
48 The number of nodes.
49 p : float
50 Probability for edge creation.
51 seed : integer, random_state, or None (default)
52 Indicator of random number generation state.
53 See :ref:`Randomness<randomness>`.
54 directed : bool, optional (default=False)
55 If True, this function returns a directed graph.
57 Notes
58 -----
59 The $G_{n,p}$ graph algorithm chooses each of the $[n (n - 1)] / 2$
60 (undirected) or $n (n - 1)$ (directed) possible edges with probability $p$.
62 This algorithm [1]_ runs in $O(n + m)$ time, where `m` is the expected number of
63 edges, which equals $p n (n - 1) / 2$. This should be faster than
64 :func:`gnp_random_graph` when $p$ is small and the expected number of edges
65 is small (that is, the graph is sparse).
67 See Also
68 --------
69 gnp_random_graph
71 References
72 ----------
73 .. [1] Vladimir Batagelj and Ulrik Brandes,
74 "Efficient generation of large random networks",
75 Phys. Rev. E, 71, 036113, 2005.
76 """
77 G = empty_graph(n)
79 if p <= 0 or p >= 1:
80 return nx.gnp_random_graph(n, p, seed=seed, directed=directed)
82 lp = math.log(1.0 - p)
84 if directed:
85 G = nx.DiGraph(G)
86 v = 1
87 w = -1
88 while v < n:
89 lr = math.log(1.0 - seed.random())
90 w = w + 1 + int(lr / lp)
91 while w >= v and v < n:
92 w = w - v
93 v = v + 1
94 if v < n:
95 G.add_edge(w, v)
97 # Nodes in graph are from 0,n-1 (start with v as the second node index).
98 v = 1
99 w = -1
100 while v < n:
101 lr = math.log(1.0 - seed.random())
102 w = w + 1 + int(lr / lp)
103 while w >= v and v < n:
104 w = w - v
105 v = v + 1
106 if v < n:
107 G.add_edge(v, w)
108 return G
111@py_random_state(2)
112@nx._dispatch(graphs=None)
113def gnp_random_graph(n, p, seed=None, directed=False):
114 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph
115 or a binomial graph.
117 The $G_{n,p}$ model chooses each of the possible edges with probability $p$.
119 Parameters
120 ----------
121 n : int
122 The number of nodes.
123 p : float
124 Probability for edge creation.
125 seed : integer, random_state, or None (default)
126 Indicator of random number generation state.
127 See :ref:`Randomness<randomness>`.
128 directed : bool, optional (default=False)
129 If True, this function returns a directed graph.
131 See Also
132 --------
133 fast_gnp_random_graph
135 Notes
136 -----
137 This algorithm [2]_ runs in $O(n^2)$ time. For sparse graphs (that is, for
138 small values of $p$), :func:`fast_gnp_random_graph` is a faster algorithm.
140 :func:`binomial_graph` and :func:`erdos_renyi_graph` are
141 aliases for :func:`gnp_random_graph`.
143 >>> nx.binomial_graph is nx.gnp_random_graph
144 True
145 >>> nx.erdos_renyi_graph is nx.gnp_random_graph
146 True
148 References
149 ----------
150 .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
151 .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
152 """
153 if directed:
154 edges = itertools.permutations(range(n), 2)
155 G = nx.DiGraph()
156 else:
157 edges = itertools.combinations(range(n), 2)
158 G = nx.Graph()
159 G.add_nodes_from(range(n))
160 if p <= 0:
161 return G
162 if p >= 1:
163 return complete_graph(n, create_using=G)
165 for e in edges:
166 if seed.random() < p:
167 G.add_edge(*e)
168 return G
171# add some aliases to common names
172binomial_graph = gnp_random_graph
173erdos_renyi_graph = gnp_random_graph
176@py_random_state(2)
177@nx._dispatch(graphs=None)
178def dense_gnm_random_graph(n, m, seed=None):
179 """Returns a $G_{n,m}$ random graph.
181 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
182 of all graphs with $n$ nodes and $m$ edges.
184 This algorithm should be faster than :func:`gnm_random_graph` for dense
185 graphs.
187 Parameters
188 ----------
189 n : int
190 The number of nodes.
191 m : int
192 The number of edges.
193 seed : integer, random_state, or None (default)
194 Indicator of random number generation state.
195 See :ref:`Randomness<randomness>`.
197 See Also
198 --------
199 gnm_random_graph
201 Notes
202 -----
203 Algorithm by Keith M. Briggs Mar 31, 2006.
204 Inspired by Knuth's Algorithm S (Selection sampling technique),
205 in section 3.4.2 of [1]_.
207 References
208 ----------
209 .. [1] Donald E. Knuth, The Art of Computer Programming,
210 Volume 2/Seminumerical algorithms, Third Edition, Addison-Wesley, 1997.
211 """
212 mmax = n * (n - 1) // 2
213 if m >= mmax:
214 G = complete_graph(n)
215 else:
216 G = empty_graph(n)
218 if n == 1 or m >= mmax:
219 return G
221 u = 0
222 v = 1
223 t = 0
224 k = 0
225 while True:
226 if seed.randrange(mmax - t) < m - k:
227 G.add_edge(u, v)
228 k += 1
229 if k == m:
230 return G
231 t += 1
232 v += 1
233 if v == n: # go to next row of adjacency matrix
234 u += 1
235 v = u + 1
238@py_random_state(2)
239@nx._dispatch(graphs=None)
240def gnm_random_graph(n, m, seed=None, directed=False):
241 """Returns a $G_{n,m}$ random graph.
243 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
244 of all graphs with $n$ nodes and $m$ edges.
246 This algorithm should be faster than :func:`dense_gnm_random_graph` for
247 sparse graphs.
249 Parameters
250 ----------
251 n : int
252 The number of nodes.
253 m : int
254 The number of edges.
255 seed : integer, random_state, or None (default)
256 Indicator of random number generation state.
257 See :ref:`Randomness<randomness>`.
258 directed : bool, optional (default=False)
259 If True return a directed graph
261 See also
262 --------
263 dense_gnm_random_graph
265 """
266 if directed:
267 G = nx.DiGraph()
268 else:
269 G = nx.Graph()
270 G.add_nodes_from(range(n))
272 if n == 1:
273 return G
274 max_edges = n * (n - 1)
275 if not directed:
276 max_edges /= 2.0
277 if m >= max_edges:
278 return complete_graph(n, create_using=G)
280 nlist = list(G)
281 edge_count = 0
282 while edge_count < m:
283 # generate random edge,u,v
284 u = seed.choice(nlist)
285 v = seed.choice(nlist)
286 if u == v or G.has_edge(u, v):
287 continue
288 else:
289 G.add_edge(u, v)
290 edge_count = edge_count + 1
291 return G
294@py_random_state(3)
295@nx._dispatch(graphs=None)
296def newman_watts_strogatz_graph(n, k, p, seed=None):
297 """Returns a Newman–Watts–Strogatz small-world graph.
299 Parameters
300 ----------
301 n : int
302 The number of nodes.
303 k : int
304 Each node is joined with its `k` nearest neighbors in a ring
305 topology.
306 p : float
307 The probability of adding a new edge for each edge.
308 seed : integer, random_state, or None (default)
309 Indicator of random number generation state.
310 See :ref:`Randomness<randomness>`.
312 Notes
313 -----
314 First create a ring over $n$ nodes [1]_. Then each node in the ring is
315 connected with its $k$ nearest neighbors (or $k - 1$ neighbors if $k$
316 is odd). Then shortcuts are created by adding new edges as follows: for
317 each edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest
318 neighbors" with probability $p$ add a new edge $(u, w)$ with
319 randomly-chosen existing node $w$. In contrast with
320 :func:`watts_strogatz_graph`, no edges are removed.
322 See Also
323 --------
324 watts_strogatz_graph
326 References
327 ----------
328 .. [1] M. E. J. Newman and D. J. Watts,
329 Renormalization group analysis of the small-world network model,
330 Physics Letters A, 263, 341, 1999.
331 https://doi.org/10.1016/S0375-9601(99)00757-4
332 """
333 if k > n:
334 raise nx.NetworkXError("k>=n, choose smaller k or larger n")
336 # If k == n the graph return is a complete graph
337 if k == n:
338 return nx.complete_graph(n)
340 G = empty_graph(n)
341 nlist = list(G.nodes())
342 fromv = nlist
343 # connect the k/2 neighbors
344 for j in range(1, k // 2 + 1):
345 tov = fromv[j:] + fromv[0:j] # the first j are now last
346 for i in range(len(fromv)):
347 G.add_edge(fromv[i], tov[i])
348 # for each edge u-v, with probability p, randomly select existing
349 # node w and add new edge u-w
350 e = list(G.edges())
351 for u, v in e:
352 if seed.random() < p:
353 w = seed.choice(nlist)
354 # no self-loops and reject if edge u-w exists
355 # is that the correct NWS model?
356 while w == u or G.has_edge(u, w):
357 w = seed.choice(nlist)
358 if G.degree(u) >= n - 1:
359 break # skip this rewiring
360 else:
361 G.add_edge(u, w)
362 return G
365@py_random_state(3)
366@nx._dispatch(graphs=None)
367def watts_strogatz_graph(n, k, p, seed=None):
368 """Returns a Watts–Strogatz small-world graph.
370 Parameters
371 ----------
372 n : int
373 The number of nodes
374 k : int
375 Each node is joined with its `k` nearest neighbors in a ring
376 topology.
377 p : float
378 The probability of rewiring each edge
379 seed : integer, random_state, or None (default)
380 Indicator of random number generation state.
381 See :ref:`Randomness<randomness>`.
383 See Also
384 --------
385 newman_watts_strogatz_graph
386 connected_watts_strogatz_graph
388 Notes
389 -----
390 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined
391 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
392 Then shortcuts are created by replacing some edges as follows: for each
393 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
394 with probability $p$ replace it with a new edge $(u, w)$ with uniformly
395 random choice of existing node $w$.
397 In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring
398 does not increase the number of edges. The rewired graph is not guaranteed
399 to be connected as in :func:`connected_watts_strogatz_graph`.
401 References
402 ----------
403 .. [1] Duncan J. Watts and Steven H. Strogatz,
404 Collective dynamics of small-world networks,
405 Nature, 393, pp. 440--442, 1998.
406 """
407 if k > n:
408 raise nx.NetworkXError("k>n, choose smaller k or larger n")
410 # If k == n, the graph is complete not Watts-Strogatz
411 if k == n:
412 return nx.complete_graph(n)
414 G = nx.Graph()
415 nodes = list(range(n)) # nodes are labeled 0 to n-1
416 # connect each node to k/2 neighbors
417 for j in range(1, k // 2 + 1):
418 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
419 G.add_edges_from(zip(nodes, targets))
420 # rewire edges from each node
421 # loop over all nodes in order (label) and neighbors in order (distance)
422 # no self loops or multiple edges allowed
423 for j in range(1, k // 2 + 1): # outer loop is neighbors
424 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
425 # inner loop in node order
426 for u, v in zip(nodes, targets):
427 if seed.random() < p:
428 w = seed.choice(nodes)
429 # Enforce no self-loops or multiple edges
430 while w == u or G.has_edge(u, w):
431 w = seed.choice(nodes)
432 if G.degree(u) >= n - 1:
433 break # skip this rewiring
434 else:
435 G.remove_edge(u, v)
436 G.add_edge(u, w)
437 return G
440@py_random_state(4)
441@nx._dispatch(graphs=None)
442def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None):
443 """Returns a connected Watts–Strogatz small-world graph.
445 Attempts to generate a connected graph by repeated generation of
446 Watts–Strogatz small-world graphs. An exception is raised if the maximum
447 number of tries is exceeded.
449 Parameters
450 ----------
451 n : int
452 The number of nodes
453 k : int
454 Each node is joined with its `k` nearest neighbors in a ring
455 topology.
456 p : float
457 The probability of rewiring each edge
458 tries : int
459 Number of attempts to generate a connected graph.
460 seed : integer, random_state, or None (default)
461 Indicator of random number generation state.
462 See :ref:`Randomness<randomness>`.
464 Notes
465 -----
466 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined
467 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
468 Then shortcuts are created by replacing some edges as follows: for each
469 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
470 with probability $p$ replace it with a new edge $(u, w)$ with uniformly
471 random choice of existing node $w$.
472 The entire process is repeated until a connected graph results.
474 See Also
475 --------
476 newman_watts_strogatz_graph
477 watts_strogatz_graph
479 References
480 ----------
481 .. [1] Duncan J. Watts and Steven H. Strogatz,
482 Collective dynamics of small-world networks,
483 Nature, 393, pp. 440--442, 1998.
484 """
485 for i in range(tries):
486 # seed is an RNG so should change sequence each call
487 G = watts_strogatz_graph(n, k, p, seed)
488 if nx.is_connected(G):
489 return G
490 raise nx.NetworkXError("Maximum number of tries exceeded")
493@py_random_state(2)
494@nx._dispatch(graphs=None)
495def random_regular_graph(d, n, seed=None):
496 r"""Returns a random $d$-regular graph on $n$ nodes.
498 A regular graph is a graph where each node has the same number of neighbors.
500 The resulting graph has no self-loops or parallel edges.
502 Parameters
503 ----------
504 d : int
505 The degree of each node.
506 n : integer
507 The number of nodes. The value of $n \times d$ must be even.
508 seed : integer, random_state, or None (default)
509 Indicator of random number generation state.
510 See :ref:`Randomness<randomness>`.
512 Notes
513 -----
514 The nodes are numbered from $0$ to $n - 1$.
516 Kim and Vu's paper [2]_ shows that this algorithm samples in an
517 asymptotically uniform way from the space of random graphs when
518 $d = O(n^{1 / 3 - \epsilon})$.
520 Raises
521 ------
523 NetworkXError
524 If $n \times d$ is odd or $d$ is greater than or equal to $n$.
526 References
527 ----------
528 .. [1] A. Steger and N. Wormald,
529 Generating random regular graphs quickly,
530 Probability and Computing 8 (1999), 377-396, 1999.
531 https://doi.org/10.1017/S0963548399003867
533 .. [2] Jeong Han Kim and Van H. Vu,
534 Generating random regular graphs,
535 Proceedings of the thirty-fifth ACM symposium on Theory of computing,
536 San Diego, CA, USA, pp 213--222, 2003.
537 http://portal.acm.org/citation.cfm?id=780542.780576
538 """
539 if (n * d) % 2 != 0:
540 raise nx.NetworkXError("n * d must be even")
542 if not 0 <= d < n:
543 raise nx.NetworkXError("the 0 <= d < n inequality must be satisfied")
545 if d == 0:
546 return empty_graph(n)
548 def _suitable(edges, potential_edges):
549 # Helper subroutine to check if there are suitable edges remaining
550 # If False, the generation of the graph has failed
551 if not potential_edges:
552 return True
553 for s1 in potential_edges:
554 for s2 in potential_edges:
555 # Two iterators on the same dictionary are guaranteed
556 # to visit it in the same order if there are no
557 # intervening modifications.
558 if s1 == s2:
559 # Only need to consider s1-s2 pair one time
560 break
561 if s1 > s2:
562 s1, s2 = s2, s1
563 if (s1, s2) not in edges:
564 return True
565 return False
567 def _try_creation():
568 # Attempt to create an edge set
570 edges = set()
571 stubs = list(range(n)) * d
573 while stubs:
574 potential_edges = defaultdict(lambda: 0)
575 seed.shuffle(stubs)
576 stubiter = iter(stubs)
577 for s1, s2 in zip(stubiter, stubiter):
578 if s1 > s2:
579 s1, s2 = s2, s1
580 if s1 != s2 and ((s1, s2) not in edges):
581 edges.add((s1, s2))
582 else:
583 potential_edges[s1] += 1
584 potential_edges[s2] += 1
586 if not _suitable(edges, potential_edges):
587 return None # failed to find suitable edge set
589 stubs = [
590 node
591 for node, potential in potential_edges.items()
592 for _ in range(potential)
593 ]
594 return edges
596 # Even though a suitable edge set exists,
597 # the generation of such a set is not guaranteed.
598 # Try repeatedly to find one.
599 edges = _try_creation()
600 while edges is None:
601 edges = _try_creation()
603 G = nx.Graph()
604 G.add_edges_from(edges)
606 return G
609def _random_subset(seq, m, rng):
610 """Return m unique elements from seq.
612 This differs from random.sample which can return repeated
613 elements if seq holds repeated elements.
615 Note: rng is a random.Random or numpy.random.RandomState instance.
616 """
617 targets = set()
618 while len(targets) < m:
619 x = rng.choice(seq)
620 targets.add(x)
621 return targets
624@py_random_state(2)
625@nx._dispatch(graphs=None)
626def barabasi_albert_graph(n, m, seed=None, initial_graph=None):
627 """Returns a random graph using Barabási–Albert preferential attachment
629 A graph of $n$ nodes is grown by attaching new nodes each with $m$
630 edges that are preferentially attached to existing nodes with high degree.
632 Parameters
633 ----------
634 n : int
635 Number of nodes
636 m : int
637 Number of edges to attach from a new node to existing nodes
638 seed : integer, random_state, or None (default)
639 Indicator of random number generation state.
640 See :ref:`Randomness<randomness>`.
641 initial_graph : Graph or None (default)
642 Initial network for Barabási–Albert algorithm.
643 It should be a connected graph for most use cases.
644 A copy of `initial_graph` is used.
645 If None, starts from a star graph on (m+1) nodes.
647 Returns
648 -------
649 G : Graph
651 Raises
652 ------
653 NetworkXError
654 If `m` does not satisfy ``1 <= m < n``, or
655 the initial graph number of nodes m0 does not satisfy ``m <= m0 <= n``.
657 References
658 ----------
659 .. [1] A. L. Barabási and R. Albert "Emergence of scaling in
660 random networks", Science 286, pp 509-512, 1999.
661 """
663 if m < 1 or m >= n:
664 raise nx.NetworkXError(
665 f"Barabási–Albert network must have m >= 1 and m < n, m = {m}, n = {n}"
666 )
668 if initial_graph is None:
669 # Default initial graph : star graph on (m + 1) nodes
670 G = star_graph(m)
671 else:
672 if len(initial_graph) < m or len(initial_graph) > n:
673 raise nx.NetworkXError(
674 f"Barabási–Albert initial graph needs between m={m} and n={n} nodes"
675 )
676 G = initial_graph.copy()
678 # List of existing nodes, with nodes repeated once for each adjacent edge
679 repeated_nodes = [n for n, d in G.degree() for _ in range(d)]
680 # Start adding the other n - m0 nodes.
681 source = len(G)
682 while source < n:
683 # Now choose m unique nodes from the existing nodes
684 # Pick uniformly from repeated_nodes (preferential attachment)
685 targets = _random_subset(repeated_nodes, m, seed)
686 # Add edges to m nodes from the source.
687 G.add_edges_from(zip([source] * m, targets))
688 # Add one node to the list for each new edge just created.
689 repeated_nodes.extend(targets)
690 # And the new node "source" has m edges to add to the list.
691 repeated_nodes.extend([source] * m)
693 source += 1
694 return G
697@py_random_state(4)
698@nx._dispatch(graphs=None)
699def dual_barabasi_albert_graph(n, m1, m2, p, seed=None, initial_graph=None):
700 """Returns a random graph using dual Barabási–Albert preferential attachment
702 A graph of $n$ nodes is grown by attaching new nodes each with either $m_1$
703 edges (with probability $p$) or $m_2$ edges (with probability $1-p$) that
704 are preferentially attached to existing nodes with high degree.
706 Parameters
707 ----------
708 n : int
709 Number of nodes
710 m1 : int
711 Number of edges to link each new node to existing nodes with probability $p$
712 m2 : int
713 Number of edges to link each new node to existing nodes with probability $1-p$
714 p : float
715 The probability of attaching $m_1$ edges (as opposed to $m_2$ edges)
716 seed : integer, random_state, or None (default)
717 Indicator of random number generation state.
718 See :ref:`Randomness<randomness>`.
719 initial_graph : Graph or None (default)
720 Initial network for Barabási–Albert algorithm.
721 A copy of `initial_graph` is used.
722 It should be connected for most use cases.
723 If None, starts from an star graph on max(m1, m2) + 1 nodes.
725 Returns
726 -------
727 G : Graph
729 Raises
730 ------
731 NetworkXError
732 If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n``, or
733 `p` does not satisfy ``0 <= p <= 1``, or
734 the initial graph number of nodes m0 does not satisfy m1, m2 <= m0 <= n.
736 References
737 ----------
738 .. [1] N. Moshiri "The dual-Barabasi-Albert model", arXiv:1810.10538.
739 """
741 if m1 < 1 or m1 >= n:
742 raise nx.NetworkXError(
743 f"Dual Barabási–Albert must have m1 >= 1 and m1 < n, m1 = {m1}, n = {n}"
744 )
745 if m2 < 1 or m2 >= n:
746 raise nx.NetworkXError(
747 f"Dual Barabási–Albert must have m2 >= 1 and m2 < n, m2 = {m2}, n = {n}"
748 )
749 if p < 0 or p > 1:
750 raise nx.NetworkXError(
751 f"Dual Barabási–Albert network must have 0 <= p <= 1, p = {p}"
752 )
754 # For simplicity, if p == 0 or 1, just return BA
755 if p == 1:
756 return barabasi_albert_graph(n, m1, seed)
757 elif p == 0:
758 return barabasi_albert_graph(n, m2, seed)
760 if initial_graph is None:
761 # Default initial graph : empty graph on max(m1, m2) nodes
762 G = star_graph(max(m1, m2))
763 else:
764 if len(initial_graph) < max(m1, m2) or len(initial_graph) > n:
765 raise nx.NetworkXError(
766 f"Barabási–Albert initial graph must have between "
767 f"max(m1, m2) = {max(m1, m2)} and n = {n} nodes"
768 )
769 G = initial_graph.copy()
771 # Target nodes for new edges
772 targets = list(G)
773 # List of existing nodes, with nodes repeated once for each adjacent edge
774 repeated_nodes = [n for n, d in G.degree() for _ in range(d)]
775 # Start adding the remaining nodes.
776 source = len(G)
777 while source < n:
778 # Pick which m to use (m1 or m2)
779 if seed.random() < p:
780 m = m1
781 else:
782 m = m2
783 # Now choose m unique nodes from the existing nodes
784 # Pick uniformly from repeated_nodes (preferential attachment)
785 targets = _random_subset(repeated_nodes, m, seed)
786 # Add edges to m nodes from the source.
787 G.add_edges_from(zip([source] * m, targets))
788 # Add one node to the list for each new edge just created.
789 repeated_nodes.extend(targets)
790 # And the new node "source" has m edges to add to the list.
791 repeated_nodes.extend([source] * m)
793 source += 1
794 return G
797@py_random_state(4)
798@nx._dispatch(graphs=None)
799def extended_barabasi_albert_graph(n, m, p, q, seed=None):
800 """Returns an extended Barabási–Albert model graph.
802 An extended Barabási–Albert model graph is a random graph constructed
803 using preferential attachment. The extended model allows new edges,
804 rewired edges or new nodes. Based on the probabilities $p$ and $q$
805 with $p + q < 1$, the growing behavior of the graph is determined as:
807 1) With $p$ probability, $m$ new edges are added to the graph,
808 starting from randomly chosen existing nodes and attached preferentially at the other end.
810 2) With $q$ probability, $m$ existing edges are rewired
811 by randomly choosing an edge and rewiring one end to a preferentially chosen node.
813 3) With $(1 - p - q)$ probability, $m$ new nodes are added to the graph
814 with edges attached preferentially.
816 When $p = q = 0$, the model behaves just like the Barabási–Alber model.
818 Parameters
819 ----------
820 n : int
821 Number of nodes
822 m : int
823 Number of edges with which a new node attaches to existing nodes
824 p : float
825 Probability value for adding an edge between existing nodes. p + q < 1
826 q : float
827 Probability value of rewiring of existing edges. p + q < 1
828 seed : integer, random_state, or None (default)
829 Indicator of random number generation state.
830 See :ref:`Randomness<randomness>`.
832 Returns
833 -------
834 G : Graph
836 Raises
837 ------
838 NetworkXError
839 If `m` does not satisfy ``1 <= m < n`` or ``1 >= p + q``
841 References
842 ----------
843 .. [1] Albert, R., & Barabási, A. L. (2000)
844 Topology of evolving networks: local events and universality
845 Physical review letters, 85(24), 5234.
846 """
847 if m < 1 or m >= n:
848 msg = f"Extended Barabasi-Albert network needs m>=1 and m<n, m={m}, n={n}"
849 raise nx.NetworkXError(msg)
850 if p + q >= 1:
851 msg = f"Extended Barabasi-Albert network needs p + q <= 1, p={p}, q={q}"
852 raise nx.NetworkXError(msg)
854 # Add m initial nodes (m0 in barabasi-speak)
855 G = empty_graph(m)
857 # List of nodes to represent the preferential attachment random selection.
858 # At the creation of the graph, all nodes are added to the list
859 # so that even nodes that are not connected have a chance to get selected,
860 # for rewiring and adding of edges.
861 # With each new edge, nodes at the ends of the edge are added to the list.
862 attachment_preference = []
863 attachment_preference.extend(range(m))
865 # Start adding the other n-m nodes. The first node is m.
866 new_node = m
867 while new_node < n:
868 a_probability = seed.random()
870 # Total number of edges of a Clique of all the nodes
871 clique_degree = len(G) - 1
872 clique_size = (len(G) * clique_degree) / 2
874 # Adding m new edges, if there is room to add them
875 if a_probability < p and G.size() <= clique_size - m:
876 # Select the nodes where an edge can be added
877 eligible_nodes = [nd for nd, deg in G.degree() if deg < clique_degree]
878 for i in range(m):
879 # Choosing a random source node from eligible_nodes
880 src_node = seed.choice(eligible_nodes)
882 # Picking a possible node that is not 'src_node' or
883 # neighbor with 'src_node', with preferential attachment
884 prohibited_nodes = list(G[src_node])
885 prohibited_nodes.append(src_node)
886 # This will raise an exception if the sequence is empty
887 dest_node = seed.choice(
888 [nd for nd in attachment_preference if nd not in prohibited_nodes]
889 )
890 # Adding the new edge
891 G.add_edge(src_node, dest_node)
893 # Appending both nodes to add to their preferential attachment
894 attachment_preference.append(src_node)
895 attachment_preference.append(dest_node)
897 # Adjusting the eligible nodes. Degree may be saturated.
898 if G.degree(src_node) == clique_degree:
899 eligible_nodes.remove(src_node)
900 if G.degree(dest_node) == clique_degree and dest_node in eligible_nodes:
901 eligible_nodes.remove(dest_node)
903 # Rewiring m edges, if there are enough edges
904 elif p <= a_probability < (p + q) and m <= G.size() < clique_size:
905 # Selecting nodes that have at least 1 edge but that are not
906 # fully connected to ALL other nodes (center of star).
907 # These nodes are the pivot nodes of the edges to rewire
908 eligible_nodes = [nd for nd, deg in G.degree() if 0 < deg < clique_degree]
909 for i in range(m):
910 # Choosing a random source node
911 node = seed.choice(eligible_nodes)
913 # The available nodes do have a neighbor at least.
914 neighbor_nodes = list(G[node])
916 # Choosing the other end that will get detached
917 src_node = seed.choice(neighbor_nodes)
919 # Picking a target node that is not 'node' or
920 # neighbor with 'node', with preferential attachment
921 neighbor_nodes.append(node)
922 dest_node = seed.choice(
923 [nd for nd in attachment_preference if nd not in neighbor_nodes]
924 )
925 # Rewire
926 G.remove_edge(node, src_node)
927 G.add_edge(node, dest_node)
929 # Adjusting the preferential attachment list
930 attachment_preference.remove(src_node)
931 attachment_preference.append(dest_node)
933 # Adjusting the eligible nodes.
934 # nodes may be saturated or isolated.
935 if G.degree(src_node) == 0 and src_node in eligible_nodes:
936 eligible_nodes.remove(src_node)
937 if dest_node in eligible_nodes:
938 if G.degree(dest_node) == clique_degree:
939 eligible_nodes.remove(dest_node)
940 else:
941 if G.degree(dest_node) == 1:
942 eligible_nodes.append(dest_node)
944 # Adding new node with m edges
945 else:
946 # Select the edges' nodes by preferential attachment
947 targets = _random_subset(attachment_preference, m, seed)
948 G.add_edges_from(zip([new_node] * m, targets))
950 # Add one node to the list for each new edge just created.
951 attachment_preference.extend(targets)
952 # The new node has m edges to it, plus itself: m + 1
953 attachment_preference.extend([new_node] * (m + 1))
954 new_node += 1
955 return G
958@py_random_state(3)
959@nx._dispatch(graphs=None)
960def powerlaw_cluster_graph(n, m, p, seed=None):
961 """Holme and Kim algorithm for growing graphs with powerlaw
962 degree distribution and approximate average clustering.
964 Parameters
965 ----------
966 n : int
967 the number of nodes
968 m : int
969 the number of random edges to add for each new node
970 p : float,
971 Probability of adding a triangle after adding a random edge
972 seed : integer, random_state, or None (default)
973 Indicator of random number generation state.
974 See :ref:`Randomness<randomness>`.
976 Notes
977 -----
978 The average clustering has a hard time getting above a certain
979 cutoff that depends on `m`. This cutoff is often quite low. The
980 transitivity (fraction of triangles to possible triangles) seems to
981 decrease with network size.
983 It is essentially the Barabási–Albert (BA) growth model with an
984 extra step that each random edge is followed by a chance of
985 making an edge to one of its neighbors too (and thus a triangle).
987 This algorithm improves on BA in the sense that it enables a
988 higher average clustering to be attained if desired.
990 It seems possible to have a disconnected graph with this algorithm
991 since the initial `m` nodes may not be all linked to a new node
992 on the first iteration like the BA model.
994 Raises
995 ------
996 NetworkXError
997 If `m` does not satisfy ``1 <= m <= n`` or `p` does not
998 satisfy ``0 <= p <= 1``.
1000 References
1001 ----------
1002 .. [1] P. Holme and B. J. Kim,
1003 "Growing scale-free networks with tunable clustering",
1004 Phys. Rev. E, 65, 026107, 2002.
1005 """
1007 if m < 1 or n < m:
1008 raise nx.NetworkXError(f"NetworkXError must have m>1 and m<n, m={m},n={n}")
1010 if p > 1 or p < 0:
1011 raise nx.NetworkXError(f"NetworkXError p must be in [0,1], p={p}")
1013 G = empty_graph(m) # add m initial nodes (m0 in barabasi-speak)
1014 repeated_nodes = list(G.nodes()) # list of existing nodes to sample from
1015 # with nodes repeated once for each adjacent edge
1016 source = m # next node is m
1017 while source < n: # Now add the other n-1 nodes
1018 possible_targets = _random_subset(repeated_nodes, m, seed)
1019 # do one preferential attachment for new node
1020 target = possible_targets.pop()
1021 G.add_edge(source, target)
1022 repeated_nodes.append(target) # add one node to list for each new link
1023 count = 1
1024 while count < m: # add m-1 more new links
1025 if seed.random() < p: # clustering step: add triangle
1026 neighborhood = [
1027 nbr
1028 for nbr in G.neighbors(target)
1029 if not G.has_edge(source, nbr) and nbr != source
1030 ]
1031 if neighborhood: # if there is a neighbor without a link
1032 nbr = seed.choice(neighborhood)
1033 G.add_edge(source, nbr) # add triangle
1034 repeated_nodes.append(nbr)
1035 count = count + 1
1036 continue # go to top of while loop
1037 # else do preferential attachment step if above fails
1038 target = possible_targets.pop()
1039 G.add_edge(source, target)
1040 repeated_nodes.append(target)
1041 count = count + 1
1043 repeated_nodes.extend([source] * m) # add source node to list m times
1044 source += 1
1045 return G
1048@py_random_state(3)
1049@nx._dispatch(graphs=None)
1050def random_lobster(n, p1, p2, seed=None):
1051 """Returns a random lobster graph.
1053 A lobster is a tree that reduces to a caterpillar when pruning all
1054 leaf nodes. A caterpillar is a tree that reduces to a path graph
1055 when pruning all leaf nodes; setting `p2` to zero produces a caterpillar.
1057 This implementation iterates on the probabilities `p1` and `p2` to add
1058 edges at levels 1 and 2, respectively. Graphs are therefore constructed
1059 iteratively with uniform randomness at each level rather than being selected
1060 uniformly at random from the set of all possible lobsters.
1062 Parameters
1063 ----------
1064 n : int
1065 The expected number of nodes in the backbone
1066 p1 : float
1067 Probability of adding an edge to the backbone
1068 p2 : float
1069 Probability of adding an edge one level beyond backbone
1070 seed : integer, random_state, or None (default)
1071 Indicator of random number generation state.
1072 See :ref:`Randomness<randomness>`.
1074 Raises
1075 ------
1076 NetworkXError
1077 If `p1` or `p2` parameters are >= 1 because the while loops would never finish.
1078 """
1079 p1, p2 = abs(p1), abs(p2)
1080 if any(p >= 1 for p in [p1, p2]):
1081 raise nx.NetworkXError("Probability values for `p1` and `p2` must both be < 1.")
1083 # a necessary ingredient in any self-respecting graph library
1084 llen = int(2 * seed.random() * n + 0.5)
1085 L = path_graph(llen)
1086 # build caterpillar: add edges to path graph with probability p1
1087 current_node = llen - 1
1088 for n in range(llen):
1089 while seed.random() < p1: # add fuzzy caterpillar parts
1090 current_node += 1
1091 L.add_edge(n, current_node)
1092 cat_node = current_node
1093 while seed.random() < p2: # add crunchy lobster bits
1094 current_node += 1
1095 L.add_edge(cat_node, current_node)
1096 return L # voila, un lobster!
1099@py_random_state(1)
1100@nx._dispatch(graphs=None)
1101def random_shell_graph(constructor, seed=None):
1102 """Returns a random shell graph for the constructor given.
1104 Parameters
1105 ----------
1106 constructor : list of three-tuples
1107 Represents the parameters for a shell, starting at the center
1108 shell. Each element of the list must be of the form `(n, m,
1109 d)`, where `n` is the number of nodes in the shell, `m` is
1110 the number of edges in the shell, and `d` is the ratio of
1111 inter-shell (next) edges to intra-shell edges. If `d` is zero,
1112 there will be no intra-shell edges, and if `d` is one there
1113 will be all possible intra-shell edges.
1114 seed : integer, random_state, or None (default)
1115 Indicator of random number generation state.
1116 See :ref:`Randomness<randomness>`.
1118 Examples
1119 --------
1120 >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)]
1121 >>> G = nx.random_shell_graph(constructor)
1123 """
1124 G = empty_graph(0)
1126 glist = []
1127 intra_edges = []
1128 nnodes = 0
1129 # create gnm graphs for each shell
1130 for n, m, d in constructor:
1131 inter_edges = int(m * d)
1132 intra_edges.append(m - inter_edges)
1133 g = nx.convert_node_labels_to_integers(
1134 gnm_random_graph(n, inter_edges, seed=seed), first_label=nnodes
1135 )
1136 glist.append(g)
1137 nnodes += n
1138 G = nx.operators.union(G, g)
1140 # connect the shells randomly
1141 for gi in range(len(glist) - 1):
1142 nlist1 = list(glist[gi])
1143 nlist2 = list(glist[gi + 1])
1144 total_edges = intra_edges[gi]
1145 edge_count = 0
1146 while edge_count < total_edges:
1147 u = seed.choice(nlist1)
1148 v = seed.choice(nlist2)
1149 if u == v or G.has_edge(u, v):
1150 continue
1151 else:
1152 G.add_edge(u, v)
1153 edge_count = edge_count + 1
1154 return G
1157@py_random_state(2)
1158@nx._dispatch(graphs=None)
1159def random_powerlaw_tree(n, gamma=3, seed=None, tries=100):
1160 """Returns a tree with a power law degree distribution.
1162 Parameters
1163 ----------
1164 n : int
1165 The number of nodes.
1166 gamma : float
1167 Exponent of the power law.
1168 seed : integer, random_state, or None (default)
1169 Indicator of random number generation state.
1170 See :ref:`Randomness<randomness>`.
1171 tries : int
1172 Number of attempts to adjust the sequence to make it a tree.
1174 Raises
1175 ------
1176 NetworkXError
1177 If no valid sequence is found within the maximum number of
1178 attempts.
1180 Notes
1181 -----
1182 A trial power law degree sequence is chosen and then elements are
1183 swapped with new elements from a powerlaw distribution until the
1184 sequence makes a tree (by checking, for example, that the number of
1185 edges is one smaller than the number of nodes).
1187 """
1188 # This call may raise a NetworkXError if the number of tries is succeeded.
1189 seq = random_powerlaw_tree_sequence(n, gamma=gamma, seed=seed, tries=tries)
1190 G = degree_sequence_tree(seq)
1191 return G
1194@py_random_state(2)
1195@nx._dispatch(graphs=None)
1196def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100):
1197 """Returns a degree sequence for a tree with a power law distribution.
1199 Parameters
1200 ----------
1201 n : int,
1202 The number of nodes.
1203 gamma : float
1204 Exponent of the power law.
1205 seed : integer, random_state, or None (default)
1206 Indicator of random number generation state.
1207 See :ref:`Randomness<randomness>`.
1208 tries : int
1209 Number of attempts to adjust the sequence to make it a tree.
1211 Raises
1212 ------
1213 NetworkXError
1214 If no valid sequence is found within the maximum number of
1215 attempts.
1217 Notes
1218 -----
1219 A trial power law degree sequence is chosen and then elements are
1220 swapped with new elements from a power law distribution until
1221 the sequence makes a tree (by checking, for example, that the number of
1222 edges is one smaller than the number of nodes).
1224 """
1225 # get trial sequence
1226 z = nx.utils.powerlaw_sequence(n, exponent=gamma, seed=seed)
1227 # round to integer values in the range [0,n]
1228 zseq = [min(n, max(round(s), 0)) for s in z]
1230 # another sequence to swap values from
1231 z = nx.utils.powerlaw_sequence(tries, exponent=gamma, seed=seed)
1232 # round to integer values in the range [0,n]
1233 swap = [min(n, max(round(s), 0)) for s in z]
1235 for deg in swap:
1236 # If this degree sequence can be the degree sequence of a tree, return
1237 # it. It can be a tree if the number of edges is one fewer than the
1238 # number of nodes, or in other words, `n - sum(zseq) / 2 == 1`. We
1239 # use an equivalent condition below that avoids floating point
1240 # operations.
1241 if 2 * n - sum(zseq) == 2:
1242 return zseq
1243 index = seed.randint(0, n - 1)
1244 zseq[index] = swap.pop()
1246 raise nx.NetworkXError(
1247 f"Exceeded max ({tries}) attempts for a valid tree sequence."
1248 )
1251@py_random_state(3)
1252@nx._dispatch(graphs=None)
1253def random_kernel_graph(n, kernel_integral, kernel_root=None, seed=None):
1254 r"""Returns an random graph based on the specified kernel.
1256 The algorithm chooses each of the $[n(n-1)]/2$ possible edges with
1257 probability specified by a kernel $\kappa(x,y)$ [1]_. The kernel
1258 $\kappa(x,y)$ must be a symmetric (in $x,y$), non-negative,
1259 bounded function.
1261 Parameters
1262 ----------
1263 n : int
1264 The number of nodes
1265 kernel_integral : function
1266 Function that returns the definite integral of the kernel $\kappa(x,y)$,
1267 $F(y,a,b) := \int_a^b \kappa(x,y)dx$
1268 kernel_root: function (optional)
1269 Function that returns the root $b$ of the equation $F(y,a,b) = r$.
1270 If None, the root is found using :func:`scipy.optimize.brentq`
1271 (this requires SciPy).
1272 seed : integer, random_state, or None (default)
1273 Indicator of random number generation state.
1274 See :ref:`Randomness<randomness>`.
1276 Notes
1277 -----
1278 The kernel is specified through its definite integral which must be
1279 provided as one of the arguments. If the integral and root of the
1280 kernel integral can be found in $O(1)$ time then this algorithm runs in
1281 time $O(n+m)$ where m is the expected number of edges [2]_.
1283 The nodes are set to integers from $0$ to $n-1$.
1285 Examples
1286 --------
1287 Generate an Erdős–Rényi random graph $G(n,c/n)$, with kernel
1288 $\kappa(x,y)=c$ where $c$ is the mean expected degree.
1290 >>> def integral(u, w, z):
1291 ... return c * (z - w)
1292 >>> def root(u, w, r):
1293 ... return r / c + w
1294 >>> c = 1
1295 >>> graph = nx.random_kernel_graph(1000, integral, root)
1297 See Also
1298 --------
1299 gnp_random_graph
1300 expected_degree_graph
1302 References
1303 ----------
1304 .. [1] Bollobás, Béla, Janson, S. and Riordan, O.
1305 "The phase transition in inhomogeneous random graphs",
1306 *Random Structures Algorithms*, 31, 3--122, 2007.
1308 .. [2] Hagberg A, Lemons N (2015),
1309 "Fast Generation of Sparse Random Kernel Graphs".
1310 PLoS ONE 10(9): e0135177, 2015. doi:10.1371/journal.pone.0135177
1311 """
1312 if kernel_root is None:
1313 import scipy as sp
1315 def kernel_root(y, a, r):
1316 def my_function(b):
1317 return kernel_integral(y, a, b) - r
1319 return sp.optimize.brentq(my_function, a, 1)
1321 graph = nx.Graph()
1322 graph.add_nodes_from(range(n))
1323 (i, j) = (1, 1)
1324 while i < n:
1325 r = -math.log(1 - seed.random()) # (1-seed.random()) in (0, 1]
1326 if kernel_integral(i / n, j / n, 1) <= r:
1327 i, j = i + 1, i + 1
1328 else:
1329 j = math.ceil(n * kernel_root(i / n, j / n, r))
1330 graph.add_edge(i - 1, j - 1)
1331 return graph