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 "random_k_lift",
39]
42@py_random_state(2)
43@nx._dispatchable(graphs=None, returns_graph=True)
44def fast_gnp_random_graph(n, p, seed=None, directed=False, *, create_using=None):
45 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph or
46 a binomial graph.
48 Parameters
49 ----------
50 n : int
51 The number of nodes.
52 p : float
53 Probability for edge creation.
54 seed : integer, random_state, or None (default)
55 Indicator of random number generation state.
56 See :ref:`Randomness<randomness>`.
57 directed : bool, optional (default=False)
58 If True, this function returns a directed graph.
59 create_using : Graph constructor, optional (default=nx.Graph or nx.DiGraph)
60 Graph type to create. If graph instance, then cleared before populated.
61 Multigraph types are not supported and raise a ``NetworkXError``.
62 By default NetworkX Graph or DiGraph are used depending on `directed`.
64 Notes
65 -----
66 The $G_{n,p}$ graph algorithm chooses each of the $[n (n - 1)] / 2$
67 (undirected) or $n (n - 1)$ (directed) possible edges with probability $p$.
69 This algorithm [1]_ runs in $O(n + m)$ time, where `m` is the expected number of
70 edges, which equals $p n (n - 1) / 2$. This should be faster than
71 :func:`gnp_random_graph` when $p$ is small and the expected number of edges
72 is small (that is, the graph is sparse).
74 See Also
75 --------
76 gnp_random_graph
78 References
79 ----------
80 .. [1] Vladimir Batagelj and Ulrik Brandes,
81 "Efficient generation of large random networks",
82 Phys. Rev. E, 71, 036113, 2005.
83 """
84 default = nx.DiGraph if directed else nx.Graph
85 create_using = check_create_using(
86 create_using, directed=directed, multigraph=False, default=default
87 )
88 if p <= 0 or p >= 1:
89 return nx.gnp_random_graph(
90 n, p, seed=seed, directed=directed, create_using=create_using
91 )
93 G = empty_graph(n, create_using=create_using)
95 lp = math.log(1.0 - p)
97 if directed:
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(w, v)
109 # Nodes in graph are from 0,n-1 (start with v as the second node index).
110 v = 1
111 w = -1
112 while v < n:
113 lr = math.log(1.0 - seed.random())
114 w = w + 1 + int(lr / lp)
115 while w >= v and v < n:
116 w = w - v
117 v = v + 1
118 if v < n:
119 G.add_edge(v, w)
120 return G
123@py_random_state(2)
124@nx._dispatchable(graphs=None, returns_graph=True)
125def gnp_random_graph(n, p, seed=None, directed=False, *, create_using=None):
126 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph
127 or a binomial graph.
129 The $G_{n,p}$ model chooses each of the possible edges with probability $p$.
131 Parameters
132 ----------
133 n : int
134 The number of nodes.
135 p : float
136 Probability for edge creation.
137 seed : integer, random_state, or None (default)
138 Indicator of random number generation state.
139 See :ref:`Randomness<randomness>`.
140 directed : bool, optional (default=False)
141 If True, this function returns a directed graph.
142 create_using : Graph constructor, optional (default=nx.Graph or nx.DiGraph)
143 Graph type to create. If graph instance, then cleared before populated.
144 Multigraph types are not supported and raise a ``NetworkXError``.
145 By default NetworkX Graph or DiGraph are used depending on `directed`.
147 See Also
148 --------
149 fast_gnp_random_graph
151 Notes
152 -----
153 This algorithm [2]_ runs in $O(n^2)$ time. For sparse graphs (that is, for
154 small values of $p$), :func:`fast_gnp_random_graph` is a faster algorithm.
156 :func:`binomial_graph` and :func:`erdos_renyi_graph` are
157 aliases for :func:`gnp_random_graph`.
159 >>> nx.binomial_graph is nx.gnp_random_graph
160 True
161 >>> nx.erdos_renyi_graph is nx.gnp_random_graph
162 True
164 References
165 ----------
166 .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
167 .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
168 """
169 default = nx.DiGraph if directed else nx.Graph
170 create_using = check_create_using(
171 create_using, directed=directed, multigraph=False, default=default
172 )
173 if p >= 1:
174 return complete_graph(n, create_using=create_using)
176 G = nx.empty_graph(n, create_using=create_using)
177 if p <= 0:
178 return G
180 edgetool = itertools.permutations if directed else itertools.combinations
181 for e in edgetool(range(n), 2):
182 if seed.random() < p:
183 G.add_edge(*e)
184 return G
187# add some aliases to common names
188binomial_graph = gnp_random_graph
189erdos_renyi_graph = gnp_random_graph
192@py_random_state(2)
193@nx._dispatchable(graphs=None, returns_graph=True)
194def dense_gnm_random_graph(n, m, seed=None, *, create_using=None):
195 """Returns a $G_{n,m}$ random graph.
197 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
198 of all graphs with $n$ nodes and $m$ edges.
200 This algorithm should be faster than :func:`gnm_random_graph` for dense
201 graphs.
203 Parameters
204 ----------
205 n : int
206 The number of nodes.
207 m : int
208 The number of edges.
209 seed : integer, random_state, or None (default)
210 Indicator of random number generation state.
211 See :ref:`Randomness<randomness>`.
212 create_using : Graph constructor, optional (default=nx.Graph)
213 Graph type to create. If graph instance, then cleared before populated.
214 Multigraph and directed types are not supported and raise a ``NetworkXError``.
216 See Also
217 --------
218 gnm_random_graph
220 Notes
221 -----
222 Algorithm by Keith M. Briggs Mar 31, 2006.
223 Inspired by Knuth's Algorithm S (Selection sampling technique),
224 in section 3.4.2 of [1]_.
226 References
227 ----------
228 .. [1] Donald E. Knuth, The Art of Computer Programming,
229 Volume 2/Seminumerical algorithms, Third Edition, Addison-Wesley, 1997.
230 """
231 create_using = check_create_using(create_using, directed=False, multigraph=False)
232 mmax = n * (n - 1) // 2
233 if m >= mmax:
234 return complete_graph(n, create_using)
235 G = empty_graph(n, create_using)
237 if n == 1:
238 return G
240 u = 0
241 v = 1
242 t = 0
243 k = 0
244 while True:
245 if seed.randrange(mmax - t) < m - k:
246 G.add_edge(u, v)
247 k += 1
248 if k == m:
249 return G
250 t += 1
251 v += 1
252 if v == n: # go to next row of adjacency matrix
253 u += 1
254 v = u + 1
257@py_random_state(2)
258@nx._dispatchable(graphs=None, returns_graph=True)
259def gnm_random_graph(n, m, seed=None, directed=False, *, create_using=None):
260 """Returns a $G_{n,m}$ random graph.
262 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
263 of all graphs with $n$ nodes and $m$ edges.
265 This algorithm should be faster than :func:`dense_gnm_random_graph` for
266 sparse graphs.
268 Parameters
269 ----------
270 n : int
271 The number of nodes.
272 m : int
273 The number of edges.
274 seed : integer, random_state, or None (default)
275 Indicator of random number generation state.
276 See :ref:`Randomness<randomness>`.
277 directed : bool, optional (default=False)
278 If True return a directed graph
279 create_using : Graph constructor, optional (default=nx.Graph or nx.DiGraph)
280 Graph type to create. If graph instance, then cleared before populated.
281 Multigraph types are not supported and raise a ``NetworkXError``.
282 By default NetworkX Graph or DiGraph are used depending on `directed`.
284 See also
285 --------
286 dense_gnm_random_graph
288 """
289 default = nx.DiGraph if directed else nx.Graph
290 create_using = check_create_using(
291 create_using, directed=directed, multigraph=False, default=default
292 )
293 if n == 1:
294 return nx.empty_graph(n, create_using=create_using)
295 max_edges = n * (n - 1) if directed else n * (n - 1) / 2.0
296 if m >= max_edges:
297 return complete_graph(n, create_using=create_using)
299 G = nx.empty_graph(n, create_using=create_using)
300 nlist = list(G)
301 edge_count = 0
302 while edge_count < m:
303 # generate random edge,u,v
304 u = seed.choice(nlist)
305 v = seed.choice(nlist)
306 if u == v or G.has_edge(u, v):
307 continue
308 else:
309 G.add_edge(u, v)
310 edge_count = edge_count + 1
311 return G
314@py_random_state(3)
315@nx._dispatchable(graphs=None, returns_graph=True)
316def newman_watts_strogatz_graph(n, k, p, seed=None, *, create_using=None):
317 """Returns a Newman–Watts–Strogatz small-world graph.
319 Parameters
320 ----------
321 n : int
322 The number of nodes.
323 k : int
324 Each node is joined with its `k` nearest neighbors in a ring
325 topology.
326 p : float
327 The probability of adding a new edge for each edge.
328 seed : integer, random_state, or None (default)
329 Indicator of random number generation state.
330 See :ref:`Randomness<randomness>`.
331 create_using : Graph constructor, optional (default=nx.Graph)
332 Graph type to create. If graph instance, then cleared before populated.
333 Multigraph and directed types are not supported and raise a ``NetworkXError``.
335 Notes
336 -----
337 First create a ring over $n$ nodes [1]_. Then each node in the ring is
338 connected with its $k$ nearest neighbors (or $k - 1$ neighbors if $k$
339 is odd). Then shortcuts are created by adding new edges as follows: for
340 each edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest
341 neighbors" with probability $p$ add a new edge $(u, w)$ with
342 randomly-chosen existing node $w$. In contrast with
343 :func:`watts_strogatz_graph`, no edges are removed.
345 See Also
346 --------
347 watts_strogatz_graph
349 References
350 ----------
351 .. [1] M. E. J. Newman and D. J. Watts,
352 Renormalization group analysis of the small-world network model,
353 Physics Letters A, 263, 341, 1999.
354 https://doi.org/10.1016/S0375-9601(99)00757-4
355 """
356 create_using = check_create_using(create_using, directed=False, multigraph=False)
357 if k > n:
358 raise nx.NetworkXError("k>=n, choose smaller k or larger n")
360 # If k == n the graph return is a complete graph
361 if k == n:
362 return nx.complete_graph(n, create_using)
364 G = empty_graph(n, create_using)
365 nlist = list(G.nodes())
366 fromv = nlist
367 # connect the k/2 neighbors
368 for j in range(1, k // 2 + 1):
369 tov = fromv[j:] + fromv[0:j] # the first j are now last
370 for i in range(len(fromv)):
371 G.add_edge(fromv[i], tov[i])
372 # for each edge u-v, with probability p, randomly select existing
373 # node w and add new edge u-w
374 e = list(G.edges())
375 for u, v in e:
376 if seed.random() < p:
377 w = seed.choice(nlist)
378 # no self-loops and reject if edge u-w exists
379 # is that the correct NWS model?
380 while w == u or G.has_edge(u, w):
381 w = seed.choice(nlist)
382 if G.degree(u) >= n - 1:
383 break # skip this rewiring
384 else:
385 G.add_edge(u, w)
386 return G
389@py_random_state(3)
390@nx._dispatchable(graphs=None, returns_graph=True)
391def watts_strogatz_graph(n, k, p, seed=None, *, create_using=None):
392 """Returns a Watts–Strogatz small-world graph.
394 Parameters
395 ----------
396 n : int
397 The number of nodes
398 k : int
399 Each node is joined with its `k` nearest neighbors in a ring
400 topology.
401 p : float
402 The probability of rewiring each edge
403 seed : integer, random_state, or None (default)
404 Indicator of random number generation state.
405 See :ref:`Randomness<randomness>`.
406 create_using : Graph constructor, optional (default=nx.Graph)
407 Graph type to create. If graph instance, then cleared before populated.
408 Multigraph and directed types are not supported and raise a ``NetworkXError``.
410 See Also
411 --------
412 newman_watts_strogatz_graph
413 connected_watts_strogatz_graph
415 Notes
416 -----
417 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined
418 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
419 Then shortcuts are created by replacing some edges as follows: for each
420 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
421 with probability $p$ replace it with a new edge $(u, w)$ with uniformly
422 random choice of existing node $w$.
424 In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring
425 does not increase the number of edges. The rewired graph is not guaranteed
426 to be connected as in :func:`connected_watts_strogatz_graph`.
428 References
429 ----------
430 .. [1] Duncan J. Watts and Steven H. Strogatz,
431 Collective dynamics of small-world networks,
432 Nature, 393, pp. 440--442, 1998.
433 """
434 create_using = check_create_using(create_using, directed=False, multigraph=False)
435 if k > n:
436 raise nx.NetworkXError("k>n, choose smaller k or larger n")
438 # If k == n, the graph is complete not Watts-Strogatz
439 if k == n:
440 G = nx.complete_graph(n, create_using)
441 return G
443 G = nx.empty_graph(n, create_using=create_using)
444 nodes = list(range(n)) # nodes are labeled 0 to n-1
445 # connect each node to k/2 neighbors
446 for j in range(1, k // 2 + 1):
447 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
448 G.add_edges_from(zip(nodes, targets))
449 # rewire edges from each node
450 # loop over all nodes in order (label) and neighbors in order (distance)
451 # no self loops or multiple edges allowed
452 for j in range(1, k // 2 + 1): # outer loop is neighbors
453 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
454 # inner loop in node order
455 for u, v in zip(nodes, targets):
456 if seed.random() < p:
457 w = seed.choice(nodes)
458 # Enforce no self-loops or multiple edges
459 while w == u or G.has_edge(u, w):
460 w = seed.choice(nodes)
461 if G.degree(u) >= n - 1:
462 break # skip this rewiring
463 else:
464 G.remove_edge(u, v)
465 G.add_edge(u, w)
466 return G
469@py_random_state(4)
470@nx._dispatchable(graphs=None, returns_graph=True)
471def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None, *, create_using=None):
472 """Returns a connected Watts–Strogatz small-world graph.
474 Attempts to generate a connected graph by repeated generation of
475 Watts–Strogatz small-world graphs. An exception is raised if the maximum
476 number of tries is exceeded.
478 Parameters
479 ----------
480 n : int
481 The number of nodes
482 k : int
483 Each node is joined with its `k` nearest neighbors in a ring
484 topology.
485 p : float
486 The probability of rewiring each edge
487 tries : int
488 Number of attempts to generate a connected graph.
489 seed : integer, random_state, or None (default)
490 Indicator of random number generation state.
491 See :ref:`Randomness<randomness>`.
492 create_using : Graph constructor, optional (default=nx.Graph)
493 Graph type to create. If graph instance, then cleared before populated.
494 Multigraph and directed types are not supported and raise a ``NetworkXError``.
496 Notes
497 -----
498 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined
499 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
500 Then shortcuts are created by replacing some edges as follows: for each
501 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
502 with probability $p$ replace it with a new edge $(u, w)$ with uniformly
503 random choice of existing node $w$.
504 The entire process is repeated until a connected graph results.
506 See Also
507 --------
508 newman_watts_strogatz_graph
509 watts_strogatz_graph
511 References
512 ----------
513 .. [1] Duncan J. Watts and Steven H. Strogatz,
514 Collective dynamics of small-world networks,
515 Nature, 393, pp. 440--442, 1998.
516 """
517 for i in range(tries):
518 # seed is an RNG so should change sequence each call
519 G = watts_strogatz_graph(n, k, p, seed, create_using=create_using)
520 if nx.is_connected(G):
521 return G
522 raise nx.NetworkXError("Maximum number of tries exceeded")
525@py_random_state(2)
526@nx._dispatchable(graphs=None, returns_graph=True)
527def random_regular_graph(d, n, seed=None, *, create_using=None):
528 r"""Returns a random $d$-regular graph on $n$ nodes.
530 A regular graph is a graph where each node has the same number of neighbors.
532 The resulting graph has no self-loops or parallel edges.
534 Parameters
535 ----------
536 d : int
537 The degree of each node.
538 n : integer
539 The number of nodes. The value of $n \times d$ must be even.
540 seed : integer, random_state, or None (default)
541 Indicator of random number generation state.
542 See :ref:`Randomness<randomness>`.
543 create_using : Graph constructor, optional (default=nx.Graph)
544 Graph type to create. If graph instance, then cleared before populated.
545 Multigraph and directed types are not supported and raise a ``NetworkXError``.
547 Notes
548 -----
549 The nodes are numbered from $0$ to $n - 1$.
551 Kim and Vu's paper [2]_ shows that this algorithm samples in an
552 asymptotically uniform way from the space of random graphs when
553 $d = O(n^{1 / 3 - \epsilon})$.
555 Raises
556 ------
558 NetworkXError
559 If $n \times d$ is odd or $d$ is greater than or equal to $n$.
561 References
562 ----------
563 .. [1] A. Steger and N. Wormald,
564 Generating random regular graphs quickly,
565 Probability and Computing 8 (1999), 377-396, 1999.
566 https://doi.org/10.1017/S0963548399003867
568 .. [2] Jeong Han Kim and Van H. Vu,
569 Generating random regular graphs,
570 Proceedings of the thirty-fifth ACM symposium on Theory of computing,
571 San Diego, CA, USA, pp 213--222, 2003.
572 http://portal.acm.org/citation.cfm?id=780542.780576
573 """
574 create_using = check_create_using(create_using, directed=False, multigraph=False)
575 if (n * d) % 2 != 0:
576 raise nx.NetworkXError("n * d must be even")
578 if not 0 <= d < n:
579 raise nx.NetworkXError("the 0 <= d < n inequality must be satisfied")
581 G = nx.empty_graph(n, create_using=create_using)
583 if d == 0:
584 return G
586 def _suitable(edges, potential_edges):
587 # Helper subroutine to check if there are suitable edges remaining
588 # If False, the generation of the graph has failed
589 if not potential_edges:
590 return True
591 for s1 in potential_edges:
592 for s2 in potential_edges:
593 # Two iterators on the same dictionary are guaranteed
594 # to visit it in the same order if there are no
595 # intervening modifications.
596 if s1 == s2:
597 # Only need to consider s1-s2 pair one time
598 break
599 if s1 > s2:
600 s1, s2 = s2, s1
601 if (s1, s2) not in edges:
602 return True
603 return False
605 def _try_creation():
606 # Attempt to create an edge set
608 edges = set()
609 stubs = list(range(n)) * d
611 while stubs:
612 potential_edges = defaultdict(lambda: 0)
613 seed.shuffle(stubs)
614 stubiter = iter(stubs)
615 for s1, s2 in zip(stubiter, stubiter):
616 if s1 > s2:
617 s1, s2 = s2, s1
618 if s1 != s2 and ((s1, s2) not in edges):
619 edges.add((s1, s2))
620 else:
621 potential_edges[s1] += 1
622 potential_edges[s2] += 1
624 if not _suitable(edges, potential_edges):
625 return None # failed to find suitable edge set
627 stubs = [
628 node
629 for node, potential in potential_edges.items()
630 for _ in range(potential)
631 ]
632 return edges
634 # Even though a suitable edge set exists,
635 # the generation of such a set is not guaranteed.
636 # Try repeatedly to find one.
637 edges = _try_creation()
638 while edges is None:
639 edges = _try_creation()
640 G.add_edges_from(edges)
642 return G
645def _random_subset(seq, m, rng):
646 """Return m unique elements from seq.
648 This differs from random.sample which can return repeated
649 elements if seq holds repeated elements.
651 Note: rng is a random.Random or numpy.random.RandomState instance.
652 """
653 targets = set()
654 while len(targets) < m:
655 x = rng.choice(seq)
656 targets.add(x)
657 return targets
660@py_random_state(2)
661@nx._dispatchable(graphs=None, returns_graph=True)
662def barabasi_albert_graph(n, m, seed=None, initial_graph=None, *, create_using=None):
663 """Returns a random graph using Barabási–Albert preferential attachment
665 A graph of $n$ nodes is grown by attaching new nodes each with $m$
666 edges that are preferentially attached to existing nodes with high degree.
668 Parameters
669 ----------
670 n : int
671 Number of nodes
672 m : int
673 Number of edges to attach from a new node to existing nodes
674 seed : integer, random_state, or None (default)
675 Indicator of random number generation state.
676 See :ref:`Randomness<randomness>`.
677 initial_graph : Graph or None (default)
678 Initial network for Barabási–Albert algorithm.
679 It should be a connected graph for most use cases.
680 A copy of `initial_graph` is used.
681 If None, starts from a star graph on (m+1) nodes.
682 create_using : Graph constructor, optional (default=nx.Graph)
683 Graph type to create. If graph instance, then cleared before populated.
684 Multigraph and directed types are not supported and raise a ``NetworkXError``.
686 Returns
687 -------
688 G : Graph
690 Raises
691 ------
692 NetworkXError
693 If `m` does not satisfy ``1 <= m < n``, or
694 the initial graph number of nodes m0 does not satisfy ``m <= m0 <= n``.
696 References
697 ----------
698 .. [1] A. L. Barabási and R. Albert "Emergence of scaling in
699 random networks", Science 286, pp 509-512, 1999.
700 """
701 create_using = check_create_using(create_using, directed=False, multigraph=False)
702 if m < 1 or m >= n:
703 raise nx.NetworkXError(
704 f"Barabási–Albert network must have m >= 1 and m < n, m = {m}, n = {n}"
705 )
707 if initial_graph is None:
708 # Default initial graph : star graph on (m + 1) nodes
709 G = star_graph(m, create_using)
710 else:
711 if len(initial_graph) < m or len(initial_graph) > n:
712 raise nx.NetworkXError(
713 f"Barabási–Albert initial graph needs between m={m} and n={n} nodes"
714 )
715 G = initial_graph.copy()
717 # List of existing nodes, with nodes repeated once for each adjacent edge
718 repeated_nodes = [n for n, d in G.degree() for _ in range(d)]
719 # Start adding the other n - m0 nodes.
720 source = len(G)
721 while source < n:
722 # Now choose m unique nodes from the existing nodes
723 # Pick uniformly from repeated_nodes (preferential attachment)
724 targets = _random_subset(repeated_nodes, m, seed)
725 # Add edges to m nodes from the source.
726 G.add_edges_from(zip([source] * m, targets))
727 # Add one node to the list for each new edge just created.
728 repeated_nodes.extend(targets)
729 # And the new node "source" has m edges to add to the list.
730 repeated_nodes.extend([source] * m)
732 source += 1
733 return G
736@py_random_state(4)
737@nx._dispatchable(graphs=None, returns_graph=True)
738def dual_barabasi_albert_graph(
739 n, m1, m2, p, seed=None, initial_graph=None, *, create_using=None
740):
741 """Returns a random graph using dual Barabási–Albert preferential attachment
743 A graph of $n$ nodes is grown by attaching new nodes each with either $m_1$
744 edges (with probability $p$) or $m_2$ edges (with probability $1-p$) that
745 are preferentially attached to existing nodes with high degree.
747 Parameters
748 ----------
749 n : int
750 Number of nodes
751 m1 : int
752 Number of edges to link each new node to existing nodes with probability $p$
753 m2 : int
754 Number of edges to link each new node to existing nodes with probability $1-p$
755 p : float
756 The probability of attaching $m_1$ edges (as opposed to $m_2$ edges)
757 seed : integer, random_state, or None (default)
758 Indicator of random number generation state.
759 See :ref:`Randomness<randomness>`.
760 initial_graph : Graph or None (default)
761 Initial network for Barabási–Albert algorithm.
762 A copy of `initial_graph` is used.
763 It should be connected for most use cases.
764 If None, starts from an star graph on max(m1, m2) + 1 nodes.
765 create_using : Graph constructor, optional (default=nx.Graph)
766 Graph type to create. If graph instance, then cleared before populated.
767 Multigraph and directed types are not supported and raise a ``NetworkXError``.
769 Returns
770 -------
771 G : Graph
773 Raises
774 ------
775 NetworkXError
776 If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n``, or
777 `p` does not satisfy ``0 <= p <= 1``, or
778 the initial graph number of nodes m0 does not satisfy m1, m2 <= m0 <= n.
780 References
781 ----------
782 .. [1] N. Moshiri "The dual-Barabasi-Albert model", arXiv:1810.10538.
783 """
784 create_using = check_create_using(create_using, directed=False, multigraph=False)
785 if m1 < 1 or m1 >= n:
786 raise nx.NetworkXError(
787 f"Dual Barabási–Albert must have m1 >= 1 and m1 < n, m1 = {m1}, n = {n}"
788 )
789 if m2 < 1 or m2 >= n:
790 raise nx.NetworkXError(
791 f"Dual Barabási–Albert must have m2 >= 1 and m2 < n, m2 = {m2}, n = {n}"
792 )
793 if p < 0 or p > 1:
794 raise nx.NetworkXError(
795 f"Dual Barabási–Albert network must have 0 <= p <= 1, p = {p}"
796 )
798 # For simplicity, if p == 0 or 1, just return BA
799 if p == 1:
800 return barabasi_albert_graph(n, m1, seed, create_using=create_using)
801 elif p == 0:
802 return barabasi_albert_graph(n, m2, seed, create_using=create_using)
804 if initial_graph is None:
805 # Default initial graph : star graph on max(m1, m2) nodes
806 G = star_graph(max(m1, m2), create_using)
807 else:
808 if len(initial_graph) < max(m1, m2) or len(initial_graph) > n:
809 raise nx.NetworkXError(
810 f"Barabási–Albert initial graph must have between "
811 f"max(m1, m2) = {max(m1, m2)} and n = {n} nodes"
812 )
813 G = initial_graph.copy()
815 # Target nodes for new edges
816 targets = list(G)
817 # List of existing nodes, with nodes repeated once for each adjacent edge
818 repeated_nodes = [n for n, d in G.degree() for _ in range(d)]
819 # Start adding the remaining nodes.
820 source = len(G)
821 while source < n:
822 # Pick which m to use (m1 or m2)
823 if seed.random() < p:
824 m = m1
825 else:
826 m = m2
827 # Now choose m unique nodes from the existing nodes
828 # Pick uniformly from repeated_nodes (preferential attachment)
829 targets = _random_subset(repeated_nodes, m, seed)
830 # Add edges to m nodes from the source.
831 G.add_edges_from(zip([source] * m, targets))
832 # Add one node to the list for each new edge just created.
833 repeated_nodes.extend(targets)
834 # And the new node "source" has m edges to add to the list.
835 repeated_nodes.extend([source] * m)
837 source += 1
838 return G
841@py_random_state(4)
842@nx._dispatchable(graphs=None, returns_graph=True)
843def extended_barabasi_albert_graph(n, m, p, q, seed=None, *, create_using=None):
844 """Returns an extended Barabási–Albert model graph.
846 An extended Barabási–Albert model graph is a random graph constructed
847 using preferential attachment. The extended model allows new edges,
848 rewired edges or new nodes. Based on the probabilities $p$ and $q$
849 with $p + q < 1$, the growing behavior of the graph is determined as:
851 1) With $p$ probability, $m$ new edges are added to the graph,
852 starting from randomly chosen existing nodes and attached preferentially at the
853 other end.
855 2) With $q$ probability, $m$ existing edges are rewired
856 by randomly choosing an edge and rewiring one end to a preferentially chosen node.
858 3) With $(1 - p - q)$ probability, $m$ new nodes are added to the graph
859 with edges attached preferentially.
861 When $p = q = 0$, the model behaves just like the Barabási–Alber model.
863 Parameters
864 ----------
865 n : int
866 Number of nodes
867 m : int
868 Number of edges with which a new node attaches to existing nodes
869 p : float
870 Probability value for adding an edge between existing nodes. p + q < 1
871 q : float
872 Probability value of rewiring of existing edges. p + q < 1
873 seed : integer, random_state, or None (default)
874 Indicator of random number generation state.
875 See :ref:`Randomness<randomness>`.
876 create_using : Graph constructor, optional (default=nx.Graph)
877 Graph type to create. If graph instance, then cleared before populated.
878 Multigraph and directed types are not supported and raise a ``NetworkXError``.
880 Returns
881 -------
882 G : Graph
884 Raises
885 ------
886 NetworkXError
887 If `m` does not satisfy ``1 <= m < n`` or ``1 >= p + q``
889 References
890 ----------
891 .. [1] Albert, R., & Barabási, A. L. (2000)
892 Topology of evolving networks: local events and universality
893 Physical review letters, 85(24), 5234.
894 """
895 create_using = check_create_using(create_using, directed=False, multigraph=False)
896 if m < 1 or m >= n:
897 msg = f"Extended Barabasi-Albert network needs m>=1 and m<n, m={m}, n={n}"
898 raise nx.NetworkXError(msg)
899 if p + q >= 1:
900 msg = f"Extended Barabasi-Albert network needs p + q <= 1, p={p}, q={q}"
901 raise nx.NetworkXError(msg)
903 # Add m initial nodes (m0 in barabasi-speak)
904 G = empty_graph(m, create_using)
906 # List of nodes to represent the preferential attachment random selection.
907 # At the creation of the graph, all nodes are added to the list
908 # so that even nodes that are not connected have a chance to get selected,
909 # for rewiring and adding of edges.
910 # With each new edge, nodes at the ends of the edge are added to the list.
911 attachment_preference = []
912 attachment_preference.extend(range(m))
914 # Start adding the other n-m nodes. The first node is m.
915 new_node = m
916 while new_node < n:
917 a_probability = seed.random()
919 # Total number of edges of a Clique of all the nodes
920 clique_degree = len(G) - 1
921 clique_size = (len(G) * clique_degree) / 2
923 # Adding m new edges, if there is room to add them
924 if a_probability < p and G.size() <= clique_size - m:
925 # Select the nodes where an edge can be added
926 eligible_nodes = [nd for nd, deg in G.degree() if deg < clique_degree]
927 for i in range(m):
928 # Choosing a random source node from eligible_nodes
929 src_node = seed.choice(eligible_nodes)
931 # Picking a possible node that is not 'src_node' or
932 # neighbor with 'src_node', with preferential attachment
933 prohibited_nodes = list(G[src_node])
934 prohibited_nodes.append(src_node)
935 # This will raise an exception if the sequence is empty
936 dest_node = seed.choice(
937 [nd for nd in attachment_preference if nd not in prohibited_nodes]
938 )
939 # Adding the new edge
940 G.add_edge(src_node, dest_node)
942 # Appending both nodes to add to their preferential attachment
943 attachment_preference.append(src_node)
944 attachment_preference.append(dest_node)
946 # Adjusting the eligible nodes. Degree may be saturated.
947 if G.degree(src_node) == clique_degree:
948 eligible_nodes.remove(src_node)
949 if G.degree(dest_node) == clique_degree and dest_node in eligible_nodes:
950 eligible_nodes.remove(dest_node)
952 # Rewiring m edges, if there are enough edges
953 elif p <= a_probability < (p + q) and m <= G.size() < clique_size:
954 # Selecting nodes that have at least 1 edge but that are not
955 # fully connected to ALL other nodes (center of star).
956 # These nodes are the pivot nodes of the edges to rewire
957 eligible_nodes = [nd for nd, deg in G.degree() if 0 < deg < clique_degree]
958 for i in range(m):
959 # Choosing a random source node
960 node = seed.choice(eligible_nodes)
962 # The available nodes do have a neighbor at least.
963 nbr_nodes = list(G[node])
965 # Choosing the other end that will get detached
966 src_node = seed.choice(nbr_nodes)
968 # Picking a target node that is not 'node' or
969 # neighbor with 'node', with preferential attachment
970 nbr_nodes.append(node)
971 dest_node = seed.choice(
972 [nd for nd in attachment_preference if nd not in nbr_nodes]
973 )
974 # Rewire
975 G.remove_edge(node, src_node)
976 G.add_edge(node, dest_node)
978 # Adjusting the preferential attachment list
979 attachment_preference.remove(src_node)
980 attachment_preference.append(dest_node)
982 # Adjusting the eligible nodes.
983 # nodes may be saturated or isolated.
984 if G.degree(src_node) == 0 and src_node in eligible_nodes:
985 eligible_nodes.remove(src_node)
986 if dest_node in eligible_nodes:
987 if G.degree(dest_node) == clique_degree:
988 eligible_nodes.remove(dest_node)
989 else:
990 if G.degree(dest_node) == 1:
991 eligible_nodes.append(dest_node)
993 # Adding new node with m edges
994 else:
995 # Select the edges' nodes by preferential attachment
996 targets = _random_subset(attachment_preference, m, seed)
997 G.add_edges_from(zip([new_node] * m, targets))
999 # Add one node to the list for each new edge just created.
1000 attachment_preference.extend(targets)
1001 # The new node has m edges to it, plus itself: m + 1
1002 attachment_preference.extend([new_node] * (m + 1))
1003 new_node += 1
1004 return G
1007@py_random_state(3)
1008@nx._dispatchable(graphs=None, returns_graph=True)
1009def powerlaw_cluster_graph(n, m, p, seed=None, *, create_using=None):
1010 """Holme and Kim algorithm for growing graphs with powerlaw
1011 degree distribution and approximate average clustering.
1013 Parameters
1014 ----------
1015 n : int
1016 the number of nodes
1017 m : int
1018 the number of random edges to add for each new node
1019 p : float,
1020 Probability of adding a triangle after adding a random edge
1021 seed : integer, random_state, or None (default)
1022 Indicator of random number generation state.
1023 See :ref:`Randomness<randomness>`.
1024 create_using : Graph constructor, optional (default=nx.Graph)
1025 Graph type to create. If graph instance, then cleared before populated.
1026 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1028 Notes
1029 -----
1030 The average clustering has a hard time getting above a certain
1031 cutoff that depends on `m`. This cutoff is often quite low. The
1032 transitivity (fraction of triangles to possible triangles) seems to
1033 decrease with network size.
1035 It is essentially the Barabási–Albert (BA) growth model with an
1036 extra step that each random edge is followed by a chance of
1037 making an edge to one of its neighbors too (and thus a triangle).
1039 This algorithm improves on BA in the sense that it enables a
1040 higher average clustering to be attained if desired.
1042 It seems possible to have a disconnected graph with this algorithm
1043 since the initial `m` nodes may not be all linked to a new node
1044 on the first iteration like the BA model.
1046 Raises
1047 ------
1048 NetworkXError
1049 If `m` does not satisfy ``1 <= m <= n`` or `p` does not
1050 satisfy ``0 <= p <= 1``.
1052 References
1053 ----------
1054 .. [1] P. Holme and B. J. Kim,
1055 "Growing scale-free networks with tunable clustering",
1056 Phys. Rev. E, 65, 026107, 2002.
1057 """
1058 create_using = check_create_using(create_using, directed=False, multigraph=False)
1059 if m < 1 or n < m:
1060 raise nx.NetworkXError(f"NetworkXError must have m>1 and m<n, m={m},n={n}")
1062 if p > 1 or p < 0:
1063 raise nx.NetworkXError(f"NetworkXError p must be in [0,1], p={p}")
1065 G = empty_graph(m, create_using) # add m initial nodes (m0 in barabasi-speak)
1066 repeated_nodes = list(G) # list of existing nodes to sample from
1067 # with nodes repeated once for each adjacent edge
1068 source = m # next node is m
1069 while source < n: # Now add the other n-1 nodes
1070 possible_targets = _random_subset(repeated_nodes, m, seed)
1071 # do one preferential attachment for new node
1072 target = possible_targets.pop()
1073 G.add_edge(source, target)
1074 repeated_nodes.append(target) # add one node to list for each new link
1075 count = 1
1076 while count < m: # add m-1 more new links
1077 if seed.random() < p: # clustering step: add triangle
1078 neighborhood = [
1079 nbr
1080 for nbr in G.neighbors(target)
1081 if not G.has_edge(source, nbr) and nbr != source
1082 ]
1083 if neighborhood: # if there is a neighbor without a link
1084 nbr = seed.choice(neighborhood)
1085 G.add_edge(source, nbr) # add triangle
1086 repeated_nodes.append(nbr)
1087 count = count + 1
1088 continue # go to top of while loop
1089 # else do preferential attachment step if above fails
1090 target = possible_targets.pop()
1091 G.add_edge(source, target)
1092 repeated_nodes.append(target)
1093 count = count + 1
1095 repeated_nodes.extend([source] * m) # add source node to list m times
1096 source += 1
1097 return G
1100@py_random_state(3)
1101@nx._dispatchable(graphs=None, returns_graph=True)
1102def random_lobster_graph(n, p1, p2, seed=None, *, create_using=None):
1103 """Returns a random lobster graph.
1105 A lobster is a tree that reduces to a caterpillar when pruning all
1106 leaf nodes. A caterpillar is a tree that reduces to a path graph
1107 when pruning all leaf nodes; setting `p2` to zero produces a caterpillar.
1109 This implementation iterates on the probabilities `p1` and `p2` to add
1110 edges at levels 1 and 2, respectively. Graphs are therefore constructed
1111 iteratively with uniform randomness at each level rather than being selected
1112 uniformly at random from the set of all possible lobsters.
1114 Parameters
1115 ----------
1116 n : int
1117 The expected number of nodes in the backbone
1118 p1 : float
1119 Probability of adding an edge to the backbone
1120 p2 : float
1121 Probability of adding an edge one level beyond backbone
1122 seed : integer, random_state, or None (default)
1123 Indicator of random number generation state.
1124 See :ref:`Randomness<randomness>`.
1125 create_using : Graph constructor, optional (default=nx.Graph)
1126 Graph type to create. If graph instance, then cleared before populated.
1127 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1129 Raises
1130 ------
1131 NetworkXError
1132 If `p1` or `p2` parameters are >= 1 because the while loops would never finish.
1133 """
1134 create_using = check_create_using(create_using, directed=False, multigraph=False)
1135 p1, p2 = abs(p1), abs(p2)
1136 if any(p >= 1 for p in [p1, p2]):
1137 raise nx.NetworkXError("Probability values for `p1` and `p2` must both be < 1.")
1139 # a necessary ingredient in any self-respecting graph library
1140 llen = int(2 * seed.random() * n + 0.5)
1141 L = path_graph(llen, create_using)
1142 # build caterpillar: add edges to path graph with probability p1
1143 current_node = llen - 1
1144 for n in range(llen):
1145 while seed.random() < p1: # add fuzzy caterpillar parts
1146 current_node += 1
1147 L.add_edge(n, current_node)
1148 cat_node = current_node
1149 while seed.random() < p2: # add crunchy lobster bits
1150 current_node += 1
1151 L.add_edge(cat_node, current_node)
1152 return L # voila, un lobster!
1155@py_random_state(3)
1156@nx._dispatchable(graphs=None, returns_graph=True)
1157def random_lobster(n, p1, p2, seed=None, *, create_using=None):
1158 """
1159 .. deprecated:: 3.5
1160 `random_lobster` is a deprecated alias
1161 for `random_lobster_graph`.
1162 Use `random_lobster_graph` instead.
1163 """
1164 import warnings
1166 warnings.warn(
1167 "`random_lobster` is deprecated, use `random_lobster_graph` instead.",
1168 category=DeprecationWarning,
1169 stacklevel=2,
1170 )
1171 return random_lobster_graph(n, p1, p2, seed=seed, create_using=create_using)
1174@py_random_state(1)
1175@nx._dispatchable(graphs=None, returns_graph=True)
1176def random_shell_graph(constructor, seed=None, *, create_using=None):
1177 """Returns a random shell graph for the constructor given.
1179 Parameters
1180 ----------
1181 constructor : list of three-tuples
1182 Represents the parameters for a shell, starting at the center
1183 shell. Each element of the list must be of the form `(n, m,
1184 d)`, where `n` is the number of nodes in the shell, `m` is
1185 the number of edges in the shell, and `d` is the ratio of
1186 inter-shell (next) edges to intra-shell edges. If `d` is zero,
1187 there will be no intra-shell edges, and if `d` is one there
1188 will be all possible intra-shell edges.
1189 seed : integer, random_state, or None (default)
1190 Indicator of random number generation state.
1191 See :ref:`Randomness<randomness>`.
1192 create_using : Graph constructor, optional (default=nx.Graph)
1193 Graph type to create. Graph instances are not supported.
1194 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1196 Examples
1197 --------
1198 >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)]
1199 >>> G = nx.random_shell_graph(constructor)
1201 """
1202 create_using = check_create_using(create_using, directed=False, multigraph=False)
1203 G = empty_graph(0, create_using)
1205 glist = []
1206 intra_edges = []
1207 nnodes = 0
1208 # create gnm graphs for each shell
1209 for n, m, d in constructor:
1210 inter_edges = int(m * d)
1211 intra_edges.append(m - inter_edges)
1212 g = nx.convert_node_labels_to_integers(
1213 gnm_random_graph(n, inter_edges, seed=seed, create_using=G.__class__),
1214 first_label=nnodes,
1215 )
1216 glist.append(g)
1217 nnodes += n
1218 G = nx.operators.union(G, g)
1220 # connect the shells randomly
1221 for gi in range(len(glist) - 1):
1222 nlist1 = list(glist[gi])
1223 nlist2 = list(glist[gi + 1])
1224 total_edges = intra_edges[gi]
1225 edge_count = 0
1226 while edge_count < total_edges:
1227 u = seed.choice(nlist1)
1228 v = seed.choice(nlist2)
1229 if u == v or G.has_edge(u, v):
1230 continue
1231 else:
1232 G.add_edge(u, v)
1233 edge_count = edge_count + 1
1234 return G
1237@py_random_state(2)
1238@nx._dispatchable(graphs=None, returns_graph=True)
1239def random_powerlaw_tree(n, gamma=3, seed=None, tries=100, *, create_using=None):
1240 """Returns a tree with a power law degree distribution.
1242 Parameters
1243 ----------
1244 n : int
1245 The number of nodes.
1246 gamma : float
1247 Exponent of the power law.
1248 seed : integer, random_state, or None (default)
1249 Indicator of random number generation state.
1250 See :ref:`Randomness<randomness>`.
1251 tries : int
1252 Number of attempts to adjust the sequence to make it a tree.
1253 create_using : Graph constructor, optional (default=nx.Graph)
1254 Graph type to create. If graph instance, then cleared before populated.
1255 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1257 Raises
1258 ------
1259 NetworkXError
1260 If no valid sequence is found within the maximum number of
1261 attempts.
1263 Notes
1264 -----
1265 A trial power law degree sequence is chosen and then elements are
1266 swapped with new elements from a powerlaw distribution until the
1267 sequence makes a tree (by checking, for example, that the number of
1268 edges is one smaller than the number of nodes).
1270 """
1271 create_using = check_create_using(create_using, directed=False, multigraph=False)
1272 # This call may raise a NetworkXError if the number of tries is succeeded.
1273 seq = random_powerlaw_tree_sequence(n, gamma=gamma, seed=seed, tries=tries)
1274 G = degree_sequence_tree(seq, create_using)
1275 return G
1278@py_random_state(2)
1279@nx._dispatchable(graphs=None)
1280def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100):
1281 """Returns a degree sequence for a tree with a power law distribution.
1283 Parameters
1284 ----------
1285 n : int,
1286 The number of nodes.
1287 gamma : float
1288 Exponent of the power law.
1289 seed : integer, random_state, or None (default)
1290 Indicator of random number generation state.
1291 See :ref:`Randomness<randomness>`.
1292 tries : int
1293 Number of attempts to adjust the sequence to make it a tree.
1295 Raises
1296 ------
1297 NetworkXError
1298 If no valid sequence is found within the maximum number of
1299 attempts.
1301 Notes
1302 -----
1303 A trial power law degree sequence is chosen and then elements are
1304 swapped with new elements from a power law distribution until
1305 the sequence makes a tree (by checking, for example, that the number of
1306 edges is one smaller than the number of nodes).
1308 """
1309 # get trial sequence
1310 z = nx.utils.powerlaw_sequence(n, exponent=gamma, seed=seed)
1311 # round to integer values in the range [0,n]
1312 zseq = [min(n, max(round(s), 0)) for s in z]
1314 # another sequence to swap values from
1315 z = nx.utils.powerlaw_sequence(tries, exponent=gamma, seed=seed)
1316 # round to integer values in the range [0,n]
1317 swap = [min(n, max(round(s), 0)) for s in z]
1319 for _ in swap:
1320 valid, _ = nx.utils.is_valid_tree_degree_sequence(zseq)
1321 if valid:
1322 return zseq
1323 index = seed.randint(0, n - 1)
1324 zseq[index] = swap.pop()
1326 raise nx.NetworkXError(
1327 f"Exceeded max ({tries}) attempts for a valid tree sequence."
1328 )
1331@py_random_state(3)
1332@nx._dispatchable(graphs=None, returns_graph=True)
1333def random_kernel_graph(
1334 n, kernel_integral, kernel_root=None, seed=None, *, create_using=None
1335):
1336 r"""Returns an random graph based on the specified kernel.
1338 The algorithm chooses each of the $[n(n-1)]/2$ possible edges with
1339 probability specified by a kernel $\kappa(x,y)$ [1]_. The kernel
1340 $\kappa(x,y)$ must be a symmetric (in $x,y$), non-negative,
1341 bounded function.
1343 Parameters
1344 ----------
1345 n : int
1346 The number of nodes
1347 kernel_integral : function
1348 Function that returns the definite integral of the kernel $\kappa(x,y)$,
1349 $F(y,a,b) := \int_a^b \kappa(x,y)dx$
1350 kernel_root: function (optional)
1351 Function that returns the root $b$ of the equation $F(y,a,b) = r$.
1352 If None, the root is found using :func:`scipy.optimize.brentq`
1353 (this requires SciPy).
1354 seed : integer, random_state, or None (default)
1355 Indicator of random number generation state.
1356 See :ref:`Randomness<randomness>`.
1357 create_using : Graph constructor, optional (default=nx.Graph)
1358 Graph type to create. If graph instance, then cleared before populated.
1359 Multigraph and directed types are not supported and raise a ``NetworkXError``.
1361 Notes
1362 -----
1363 The kernel is specified through its definite integral which must be
1364 provided as one of the arguments. If the integral and root of the
1365 kernel integral can be found in $O(1)$ time then this algorithm runs in
1366 time $O(n+m)$ where m is the expected number of edges [2]_.
1368 The nodes are set to integers from $0$ to $n-1$.
1370 Examples
1371 --------
1372 Generate an Erdős–Rényi random graph $G(n,c/n)$, with kernel
1373 $\kappa(x,y)=c$ where $c$ is the mean expected degree.
1375 >>> def integral(u, w, z):
1376 ... return c * (z - w)
1377 >>> def root(u, w, r):
1378 ... return r / c + w
1379 >>> c = 1
1380 >>> graph = nx.random_kernel_graph(1000, integral, root)
1382 See Also
1383 --------
1384 gnp_random_graph
1385 expected_degree_graph
1387 References
1388 ----------
1389 .. [1] Bollobás, Béla, Janson, S. and Riordan, O.
1390 "The phase transition in inhomogeneous random graphs",
1391 *Random Structures Algorithms*, 31, 3--122, 2007.
1393 .. [2] Hagberg A, Lemons N (2015),
1394 "Fast Generation of Sparse Random Kernel Graphs".
1395 PLoS ONE 10(9): e0135177, 2015. doi:10.1371/journal.pone.0135177
1396 """
1397 create_using = check_create_using(create_using, directed=False, multigraph=False)
1398 if kernel_root is None:
1399 import scipy as sp
1401 def kernel_root(y, a, r):
1402 def my_function(b):
1403 return kernel_integral(y, a, b) - r
1405 return sp.optimize.brentq(my_function, a, 1)
1407 graph = nx.empty_graph(create_using=create_using)
1408 graph.add_nodes_from(range(n))
1409 (i, j) = (1, 1)
1410 while i < n:
1411 r = -math.log(1 - seed.random()) # (1-seed.random()) in (0, 1]
1412 if kernel_integral(i / n, j / n, 1) <= r:
1413 i, j = i + 1, i + 1
1414 else:
1415 j = math.ceil(n * kernel_root(i / n, j / n, r))
1416 graph.add_edge(i - 1, j - 1)
1417 return graph
1420@py_random_state("seed")
1421@nx._dispatchable(graphs=None, returns_graph=True)
1422def random_k_lift(G, k, seed=None):
1423 r"""Return a `k`-lift of a graph using random permutations.
1425 The resulting graph ``H`` has `k` copies of each node from `G`.
1426 For each edge ``(u, v)`` in `G`, a random permutation is used to connect the ``i``-th copy of ``u``
1427 to the permuted ``i``-th copy of ``v`` in ``H``.
1429 Parameters
1430 ----------
1431 G : Graph, DiGraph, MultiGraph, or MultiDiGraph
1432 The base graph to lift. Any standard NetworkX graph type is supported.
1433 k : int
1434 The lift parameter. Each node in `G` is expanded to `k` copies.
1435 seed : int, RandomState, or None (default: None)
1436 Seed for the random number generator (used for permutation generation).
1437 This ensures reproducibility.
1438 See :ref:`Randomness<randomness>`.
1440 Returns
1441 -------
1442 H : Graph, DiGraph, MultiGraph, or MultiDiGraph
1443 The resulting `k`-lifted graph. The returned type matches the input graph type.
1445 Notes
1446 -----
1447 Given a base graph `G` and a lift parameter `k`, this function performs a `k`-lift as follows:
1448 - For each node ``v`` in `G`, it creates `k` copies: ``(v, 0), ..., (v, k - 1)``.
1449 - For each edge ``(u, v)`` in `G`, a random permutation ``σ`` is applied to determine new edges:
1450 if ``σ(i) = j``, then ``((u, i), (v, j))`` is added to ``H``.
1451 The permutation is simulated by creating a shuffled list ``permutation`` of values 0 to ``k - 1``.
1452 Each ``i``-th copy of ``u`` is then connected to the ``permutation[i]``-th copy of ``v``.
1454 This operation is often used in the construction of expander graphs [1].
1455 If the base graph is a decent expander (i.e., has a good spectral gap-the
1456 difference between the two largest eigenvalues (in absolute value) of its adjacency matrix),
1457 then its `k`-lifts are also expanders, with the spectral gap preserved
1458 (or slightly reduced and stabilizing for larger `k` [3]) with high probability,
1459 while producing a larger graph of the same degree.
1461 For arbitrary input graphs, the lifted graph may be disconnected.
1462 Disconnected lifts occur more often when the base graph is a poor expander.
1463 Since enforcing connectivity in such cases is unlikely to
1464 produce a good expander, this implementation returns the lift directly,
1465 even if it is disconnected. Users who require connected results may wrap
1466 this function with retries until a connected lift is found.
1468 This implementation supports all standard NetworkX graph types.
1469 While expander graphs are most commonly studied as degree-regular undirected simple graphs/multigraphs,
1470 the `k`-lift operation itself is well-defined and can also be beneficial for directed [4]
1471 and non-regular [5] graphs.
1473 References
1474 ----------
1475 [1] Y. Bilu and N. Linial, "Lifts, Discrepancy and Nearly Optimal Spectral Gap."
1476 *Combinatorica*, 26(5), pp. 495–519, 2006,
1477 https://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf
1478 [2] A. Valadarsky, G. Shahaf, M. Dinitz and M. Schapira,
1479 "Xpander: Towards Optimal-Performance Datacenters.",
1480 In *Proceedings of the 12th International Conference on
1481 Emerging Networking Experiments and Technologies (CoNEXT)*, 2016,
1482 https://dl.acm.org/doi/pdf/10.1145/2999572.2999580
1483 [3] N. Agarwal, K. Chandrasekaran, A. Kolla and V. Madan,
1484 "On the Expansion of Group-Based Lifts.", arXiv preprint arXiv:1311.3268v2, 2016,
1485 http://arxiv.org/abs/1311.3268v2
1486 [4] P. Chebolu and A. Frieze,
1487 "Hamilton Cycles in Random Lifts of Directed Graphs.",
1488 Department of Mathematics, Carnegie Mellon University, 2007,
1489 https://www.math.cmu.edu/~af1p/Texfiles/LiftHamDir.pdf
1490 [5] S. Hoory,
1491 "On the Girth of Graph Lifts." arXiv:2401.01238v1, 2024,
1492 https://arxiv.org/pdf/2401.01238
1494 Examples
1495 --------
1496 >>> G = nx.complete_graph(4) # 3-regular, connected graph
1497 >>> H = nx.random_k_lift(G, 4, seed=42) # 4-lift of G
1498 >>> H.number_of_nodes()
1499 16
1500 """
1501 H = G.__class__()
1503 # Create k copies of each node
1504 H.add_nodes_from((v, i) for v in G.nodes for i in range(k))
1506 # Apply random permutation to edges
1507 edges = []
1508 permutation = list(range(k))
1509 for u, v in G.edges():
1510 seed.shuffle(permutation)
1511 edges.extend(((u, i), (v, permutation[i])) for i in range(k))
1512 H.add_edges_from(edges)
1514 return H