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"""Generate graphs with a given degree sequence or expected degree sequence."""
3import heapq
4import math
5from itertools import chain, combinations, zip_longest
6from operator import itemgetter
8import networkx as nx
9from networkx.utils import py_random_state, random_weighted_sample
11__all__ = [
12 "configuration_model",
13 "directed_configuration_model",
14 "expected_degree_graph",
15 "havel_hakimi_graph",
16 "directed_havel_hakimi_graph",
17 "degree_sequence_tree",
18 "random_degree_sequence_graph",
19]
21chaini = chain.from_iterable
24def _to_stublist(degree_sequence):
25 """Returns a list of degree-repeated node numbers.
27 ``degree_sequence`` is a list of nonnegative integers representing
28 the degrees of nodes in a graph.
30 This function returns a list of node numbers with multiplicities
31 according to the given degree sequence. For example, if the first
32 element of ``degree_sequence`` is ``3``, then the first node number,
33 ``0``, will appear at the head of the returned list three times. The
34 node numbers are assumed to be the numbers zero through
35 ``len(degree_sequence) - 1``.
37 Examples
38 --------
40 >>> degree_sequence = [1, 2, 3]
41 >>> _to_stublist(degree_sequence)
42 [0, 1, 1, 2, 2, 2]
44 If a zero appears in the sequence, that means the node exists but
45 has degree zero, so that number will be skipped in the returned
46 list::
48 >>> degree_sequence = [2, 0, 1]
49 >>> _to_stublist(degree_sequence)
50 [0, 0, 2]
52 """
53 return list(chaini([n] * d for n, d in enumerate(degree_sequence)))
56def _configuration_model(
57 deg_sequence, create_using, directed=False, in_deg_sequence=None, seed=None
58):
59 """Helper function for generating either undirected or directed
60 configuration model graphs.
62 ``deg_sequence`` is a list of nonnegative integers representing the
63 degree of the node whose label is the index of the list element.
65 ``create_using`` see :func:`~networkx.empty_graph`.
67 ``directed`` and ``in_deg_sequence`` are required if you want the
68 returned graph to be generated using the directed configuration
69 model algorithm. If ``directed`` is ``False``, then ``deg_sequence``
70 is interpreted as the degree sequence of an undirected graph and
71 ``in_deg_sequence`` is ignored. Otherwise, if ``directed`` is
72 ``True``, then ``deg_sequence`` is interpreted as the out-degree
73 sequence and ``in_deg_sequence`` as the in-degree sequence of a
74 directed graph.
76 .. note::
78 ``deg_sequence`` and ``in_deg_sequence`` need not be the same
79 length.
81 ``seed`` is a random.Random or numpy.random.RandomState instance
83 This function returns a graph, directed if and only if ``directed``
84 is ``True``, generated according to the configuration model
85 algorithm. For more information on the algorithm, see the
86 :func:`configuration_model` or :func:`directed_configuration_model`
87 functions.
89 """
90 n = len(deg_sequence)
91 G = nx.empty_graph(n, create_using)
92 # If empty, return the null graph immediately.
93 if n == 0:
94 return G
95 # Build a list of available degree-repeated nodes. For example,
96 # for degree sequence [3, 2, 1, 1, 1], the "stub list" is
97 # initially [0, 0, 0, 1, 1, 2, 3, 4], that is, node 0 has degree
98 # 3 and thus is repeated 3 times, etc.
99 #
100 # Also, shuffle the stub list in order to get a random sequence of
101 # node pairs.
102 if directed:
103 pairs = zip_longest(deg_sequence, in_deg_sequence, fillvalue=0)
104 # Unzip the list of pairs into a pair of lists.
105 out_deg, in_deg = zip(*pairs)
107 out_stublist = _to_stublist(out_deg)
108 in_stublist = _to_stublist(in_deg)
110 seed.shuffle(out_stublist)
111 seed.shuffle(in_stublist)
112 else:
113 stublist = _to_stublist(deg_sequence)
114 # Choose a random balanced bipartition of the stublist, which
115 # gives a random pairing of nodes. In this implementation, we
116 # shuffle the list and then split it in half.
117 n = len(stublist)
118 half = n // 2
119 seed.shuffle(stublist)
120 out_stublist, in_stublist = stublist[:half], stublist[half:]
121 G.add_edges_from(zip(out_stublist, in_stublist))
122 return G
125@py_random_state(2)
126@nx._dispatchable(graphs=None, returns_graph=True)
127def configuration_model(deg_sequence, create_using=None, seed=None):
128 """Returns a random graph with the given degree sequence.
130 The configuration model generates a random pseudograph (graph with
131 parallel edges and self loops) by randomly assigning edges to
132 match the given degree sequence.
134 Parameters
135 ----------
136 deg_sequence : list of nonnegative integers
137 Each list entry corresponds to the degree of a node.
138 create_using : NetworkX graph constructor, optional (default MultiGraph)
139 Graph type to create. If graph instance, then cleared before populated.
140 seed : integer, random_state, or None (default)
141 Indicator of random number generation state.
142 See :ref:`Randomness<randomness>`.
144 Returns
145 -------
146 G : MultiGraph
147 A graph with the specified degree sequence.
148 Nodes are labeled starting at 0 with an index
149 corresponding to the position in deg_sequence.
151 Raises
152 ------
153 NetworkXError
154 If the degree sequence does not have an even sum.
156 See Also
157 --------
158 is_graphical
160 Notes
161 -----
162 As described by Newman [1]_.
164 A non-graphical degree sequence (not realizable by some simple
165 graph) is allowed since this function returns graphs with self
166 loops and parallel edges. An exception is raised if the degree
167 sequence does not have an even sum.
169 This configuration model construction process can lead to
170 duplicate edges and loops. You can remove the self-loops and
171 parallel edges (see below) which will likely result in a graph
172 that doesn't have the exact degree sequence specified.
174 The density of self-loops and parallel edges tends to decrease as
175 the number of nodes increases. However, typically the number of
176 self-loops will approach a Poisson distribution with a nonzero mean,
177 and similarly for the number of parallel edges. Consider a node
178 with *k* stubs. The probability of being joined to another stub of
179 the same node is basically (*k* - *1*) / *N*, where *k* is the
180 degree and *N* is the number of nodes. So the probability of a
181 self-loop scales like *c* / *N* for some constant *c*. As *N* grows,
182 this means we expect *c* self-loops. Similarly for parallel edges.
184 References
185 ----------
186 .. [1] M.E.J. Newman, "The structure and function of complex networks",
187 SIAM REVIEW 45-2, pp 167-256, 2003.
189 Examples
190 --------
191 You can create a degree sequence following a particular distribution
192 by using the one of the distribution functions in
193 :mod:`~networkx.utils.random_sequence` (or one of your own). For
194 example, to create an undirected multigraph on one hundred nodes
195 with degree sequence chosen from the power law distribution:
197 >>> sequence = nx.random_powerlaw_tree_sequence(100, tries=5000)
198 >>> G = nx.configuration_model(sequence)
199 >>> len(G)
200 100
201 >>> actual_degrees = [d for v, d in G.degree()]
202 >>> actual_degrees == sequence
203 True
205 The returned graph is a multigraph, which may have parallel
206 edges. To remove any parallel edges from the returned graph:
208 >>> G = nx.Graph(G)
210 Similarly, to remove self-loops:
212 >>> G.remove_edges_from(nx.selfloop_edges(G))
214 """
215 if sum(deg_sequence) % 2 != 0:
216 msg = "Invalid degree sequence: sum of degrees must be even, not odd"
217 raise nx.NetworkXError(msg)
219 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
220 if G.is_directed():
221 raise nx.NetworkXNotImplemented("not implemented for directed graphs")
223 G = _configuration_model(deg_sequence, G, seed=seed)
225 return G
228@py_random_state(3)
229@nx._dispatchable(graphs=None, returns_graph=True)
230def directed_configuration_model(
231 in_degree_sequence, out_degree_sequence, create_using=None, seed=None
232):
233 """Returns a directed_random graph with the given degree sequences.
235 The configuration model generates a random directed pseudograph
236 (graph with parallel edges and self loops) by randomly assigning
237 edges to match the given degree sequences.
239 Parameters
240 ----------
241 in_degree_sequence : list of nonnegative integers
242 Each list entry corresponds to the in-degree of a node.
243 out_degree_sequence : list of nonnegative integers
244 Each list entry corresponds to the out-degree of a node.
245 create_using : NetworkX graph constructor, optional (default MultiDiGraph)
246 Graph type to create. If graph instance, then cleared before populated.
247 seed : integer, random_state, or None (default)
248 Indicator of random number generation state.
249 See :ref:`Randomness<randomness>`.
251 Returns
252 -------
253 G : MultiDiGraph
254 A graph with the specified degree sequences.
255 Nodes are labeled starting at 0 with an index
256 corresponding to the position in deg_sequence.
258 Raises
259 ------
260 NetworkXError
261 If the degree sequences do not have the same sum.
263 See Also
264 --------
265 configuration_model
267 Notes
268 -----
269 Algorithm as described by Newman [1]_.
271 A non-graphical degree sequence (not realizable by some simple
272 graph) is allowed since this function returns graphs with self
273 loops and parallel edges. An exception is raised if the degree
274 sequences does not have the same sum.
276 This configuration model construction process can lead to
277 duplicate edges and loops. You can remove the self-loops and
278 parallel edges (see below) which will likely result in a graph
279 that doesn't have the exact degree sequence specified. This
280 "finite-size effect" decreases as the size of the graph increases.
282 References
283 ----------
284 .. [1] Newman, M. E. J. and Strogatz, S. H. and Watts, D. J.
285 Random graphs with arbitrary degree distributions and their applications
286 Phys. Rev. E, 64, 026118 (2001)
288 Examples
289 --------
290 One can modify the in- and out-degree sequences from an existing
291 directed graph in order to create a new directed graph. For example,
292 here we modify the directed path graph:
294 >>> D = nx.DiGraph([(0, 1), (1, 2), (2, 3)])
295 >>> din = list(d for n, d in D.in_degree())
296 >>> dout = list(d for n, d in D.out_degree())
297 >>> din.append(1)
298 >>> dout[0] = 2
299 >>> # We now expect an edge from node 0 to a new node, node 3.
300 ... D = nx.directed_configuration_model(din, dout)
302 The returned graph is a directed multigraph, which may have parallel
303 edges. To remove any parallel edges from the returned graph:
305 >>> D = nx.DiGraph(D)
307 Similarly, to remove self-loops:
309 >>> D.remove_edges_from(nx.selfloop_edges(D))
311 """
312 if sum(in_degree_sequence) != sum(out_degree_sequence):
313 msg = "Invalid degree sequences: sequences must have equal sums"
314 raise nx.NetworkXError(msg)
316 if create_using is None:
317 create_using = nx.MultiDiGraph
319 G = _configuration_model(
320 out_degree_sequence,
321 create_using,
322 directed=True,
323 in_deg_sequence=in_degree_sequence,
324 seed=seed,
325 )
327 name = "directed configuration_model {} nodes {} edges"
328 return G
331@py_random_state(1)
332@nx._dispatchable(graphs=None, returns_graph=True)
333def expected_degree_graph(w, seed=None, selfloops=True):
334 r"""Returns a random graph with given expected degrees.
336 Given a sequence of expected degrees $W=(w_0,w_1,\ldots,w_{n-1})$
337 of length $n$ this algorithm assigns an edge between node $u$ and
338 node $v$ with probability
340 .. math::
342 p_{uv} = \frac{w_u w_v}{\sum_k w_k} .
344 Parameters
345 ----------
346 w : list
347 The list of expected degrees.
348 selfloops: bool (default=True)
349 Set to False to remove the possibility of self-loop edges.
350 seed : integer, random_state, or None (default)
351 Indicator of random number generation state.
352 See :ref:`Randomness<randomness>`.
354 Returns
355 -------
356 Graph
358 Examples
359 --------
360 >>> z = [10 for i in range(100)]
361 >>> G = nx.expected_degree_graph(z)
363 Notes
364 -----
365 The nodes have integer labels corresponding to index of expected degrees
366 input sequence.
368 The complexity of this algorithm is $\mathcal{O}(n+m)$ where $n$ is the
369 number of nodes and $m$ is the expected number of edges.
371 The model in [1]_ includes the possibility of self-loop edges.
372 Set selfloops=False to produce a graph without self loops.
374 For finite graphs this model doesn't produce exactly the given
375 expected degree sequence. Instead the expected degrees are as
376 follows.
378 For the case without self loops (selfloops=False),
380 .. math::
382 E[deg(u)] = \sum_{v \ne u} p_{uv}
383 = w_u \left( 1 - \frac{w_u}{\sum_k w_k} \right) .
386 NetworkX uses the standard convention that a self-loop edge counts 2
387 in the degree of a node, so with self loops (selfloops=True),
389 .. math::
391 E[deg(u)] = \sum_{v \ne u} p_{uv} + 2 p_{uu}
392 = w_u \left( 1 + \frac{w_u}{\sum_k w_k} \right) .
394 References
395 ----------
396 .. [1] Fan Chung and L. Lu, Connected components in random graphs with
397 given expected degree sequences, Ann. Combinatorics, 6,
398 pp. 125-145, 2002.
399 .. [2] Joel Miller and Aric Hagberg,
400 Efficient generation of networks with given expected degrees,
401 in Algorithms and Models for the Web-Graph (WAW 2011),
402 Alan Frieze, Paul Horn, and Paweł Prałat (Eds), LNCS 6732,
403 pp. 115-126, 2011.
404 """
405 n = len(w)
406 G = nx.empty_graph(n)
408 # If there are no nodes are no edges in the graph, return the empty graph.
409 if n == 0 or max(w) == 0:
410 return G
412 rho = 1 / sum(w)
413 # Sort the weights in decreasing order. The original order of the
414 # weights dictates the order of the (integer) node labels, so we
415 # need to remember the permutation applied in the sorting.
416 order = sorted(enumerate(w), key=itemgetter(1), reverse=True)
417 mapping = {c: u for c, (u, v) in enumerate(order)}
418 seq = [v for u, v in order]
419 last = n
420 if not selfloops:
421 last -= 1
422 for u in range(last):
423 v = u
424 if not selfloops:
425 v += 1
426 factor = seq[u] * rho
427 p = min(seq[v] * factor, 1)
428 while v < n and p > 0:
429 if p != 1:
430 r = seed.random()
431 v += math.floor(math.log(r, 1 - p))
432 if v < n:
433 q = min(seq[v] * factor, 1)
434 if seed.random() < q / p:
435 G.add_edge(mapping[u], mapping[v])
436 v += 1
437 p = q
438 return G
441@nx._dispatchable(graphs=None, returns_graph=True)
442def havel_hakimi_graph(deg_sequence, create_using=None):
443 """Returns a simple graph with given degree sequence constructed
444 using the Havel-Hakimi algorithm.
446 Parameters
447 ----------
448 deg_sequence: list of integers
449 Each integer corresponds to the degree of a node (need not be sorted).
450 create_using : NetworkX graph constructor, optional (default=nx.Graph)
451 Graph type to create. If graph instance, then cleared before populated.
452 Directed graphs are not allowed.
454 Raises
455 ------
456 NetworkXException
457 For a non-graphical degree sequence (i.e. one
458 not realizable by some simple graph).
460 Notes
461 -----
462 The Havel-Hakimi algorithm constructs a simple graph by
463 successively connecting the node of highest degree to other nodes
464 of highest degree, resorting remaining nodes by degree, and
465 repeating the process. The resulting graph has a high
466 degree-associativity. Nodes are labeled 1,.., len(deg_sequence),
467 corresponding to their position in deg_sequence.
469 The basic algorithm is from Hakimi [1]_ and was generalized by
470 Kleitman and Wang [2]_.
472 References
473 ----------
474 .. [1] Hakimi S., On Realizability of a Set of Integers as
475 Degrees of the Vertices of a Linear Graph. I,
476 Journal of SIAM, 10(3), pp. 496-506 (1962)
477 .. [2] Kleitman D.J. and Wang D.L.
478 Algorithms for Constructing Graphs and Digraphs with Given Valences
479 and Factors Discrete Mathematics, 6(1), pp. 79-88 (1973)
480 """
481 if not nx.is_graphical(deg_sequence):
482 raise nx.NetworkXError("Invalid degree sequence")
484 p = len(deg_sequence)
485 G = nx.empty_graph(p, create_using)
486 if G.is_directed():
487 raise nx.NetworkXError("Directed graphs are not supported")
488 num_degs = [[] for i in range(p)]
489 dmax, dsum, n = 0, 0, 0
490 for d in deg_sequence:
491 # Process only the non-zero integers
492 if d > 0:
493 num_degs[d].append(n)
494 dmax, dsum, n = max(dmax, d), dsum + d, n + 1
495 # Return graph if no edges
496 if n == 0:
497 return G
499 modstubs = [(0, 0)] * (dmax + 1)
500 # Successively reduce degree sequence by removing the maximum degree
501 while n > 0:
502 # Retrieve the maximum degree in the sequence
503 while len(num_degs[dmax]) == 0:
504 dmax -= 1
505 # If there are not enough stubs to connect to, then the sequence is
506 # not graphical
507 if dmax > n - 1:
508 raise nx.NetworkXError("Non-graphical integer sequence")
510 # Remove largest stub in list
511 source = num_degs[dmax].pop()
512 n -= 1
513 # Reduce the next dmax largest stubs
514 mslen = 0
515 k = dmax
516 for i in range(dmax):
517 while len(num_degs[k]) == 0:
518 k -= 1
519 target = num_degs[k].pop()
520 G.add_edge(source, target)
521 n -= 1
522 if k > 1:
523 modstubs[mslen] = (k - 1, target)
524 mslen += 1
525 # Add back to the list any nonzero stubs that were removed
526 for i in range(mslen):
527 (stubval, stubtarget) = modstubs[i]
528 num_degs[stubval].append(stubtarget)
529 n += 1
531 return G
534@nx._dispatchable(graphs=None, returns_graph=True)
535def directed_havel_hakimi_graph(in_deg_sequence, out_deg_sequence, create_using=None):
536 """Returns a directed graph with the given degree sequences.
538 Parameters
539 ----------
540 in_deg_sequence : list of integers
541 Each list entry corresponds to the in-degree of a node.
542 out_deg_sequence : list of integers
543 Each list entry corresponds to the out-degree of a node.
544 create_using : NetworkX graph constructor, optional (default DiGraph)
545 Graph type to create. If graph instance, then cleared before populated.
547 Returns
548 -------
549 G : DiGraph
550 A graph with the specified degree sequences.
551 Nodes are labeled starting at 0 with an index
552 corresponding to the position in deg_sequence
554 Raises
555 ------
556 NetworkXError
557 If the degree sequences are not digraphical.
559 See Also
560 --------
561 configuration_model
563 Notes
564 -----
565 Algorithm as described by Kleitman and Wang [1]_.
567 References
568 ----------
569 .. [1] D.J. Kleitman and D.L. Wang
570 Algorithms for Constructing Graphs and Digraphs with Given Valences
571 and Factors Discrete Mathematics, 6(1), pp. 79-88 (1973)
572 """
573 in_deg_sequence = nx.utils.make_list_of_ints(in_deg_sequence)
574 out_deg_sequence = nx.utils.make_list_of_ints(out_deg_sequence)
576 # Process the sequences and form two heaps to store degree pairs with
577 # either zero or nonzero out degrees
578 sumin, sumout = 0, 0
579 nin, nout = len(in_deg_sequence), len(out_deg_sequence)
580 maxn = max(nin, nout)
581 G = nx.empty_graph(maxn, create_using, default=nx.DiGraph)
582 if maxn == 0:
583 return G
584 maxin = 0
585 stubheap, zeroheap = [], []
586 for n in range(maxn):
587 in_deg, out_deg = 0, 0
588 if n < nout:
589 out_deg = out_deg_sequence[n]
590 if n < nin:
591 in_deg = in_deg_sequence[n]
592 if in_deg < 0 or out_deg < 0:
593 raise nx.NetworkXError(
594 "Invalid degree sequences. Sequence values must be positive."
595 )
596 sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg)
597 if in_deg > 0:
598 stubheap.append((-1 * out_deg, -1 * in_deg, n))
599 elif out_deg > 0:
600 zeroheap.append((-1 * out_deg, n))
601 if sumin != sumout:
602 raise nx.NetworkXError(
603 "Invalid degree sequences. Sequences must have equal sums."
604 )
605 heapq.heapify(stubheap)
606 heapq.heapify(zeroheap)
608 modstubs = [(0, 0, 0)] * (maxin + 1)
609 # Successively reduce degree sequence by removing the maximum
610 while stubheap:
611 # Remove first value in the sequence with a non-zero in degree
612 (freeout, freein, target) = heapq.heappop(stubheap)
613 freein *= -1
614 if freein > len(stubheap) + len(zeroheap):
615 raise nx.NetworkXError("Non-digraphical integer sequence")
617 # Attach arcs from the nodes with the most stubs
618 mslen = 0
619 for i in range(freein):
620 if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0][0]):
621 (stubout, stubsource) = heapq.heappop(zeroheap)
622 stubin = 0
623 else:
624 (stubout, stubin, stubsource) = heapq.heappop(stubheap)
625 if stubout == 0:
626 raise nx.NetworkXError("Non-digraphical integer sequence")
627 G.add_edge(stubsource, target)
628 # Check if source is now totally connected
629 if stubout + 1 < 0 or stubin < 0:
630 modstubs[mslen] = (stubout + 1, stubin, stubsource)
631 mslen += 1
633 # Add the nodes back to the heaps that still have available stubs
634 for i in range(mslen):
635 stub = modstubs[i]
636 if stub[1] < 0:
637 heapq.heappush(stubheap, stub)
638 else:
639 heapq.heappush(zeroheap, (stub[0], stub[2]))
640 if freeout < 0:
641 heapq.heappush(zeroheap, (freeout, target))
643 return G
646@nx._dispatchable(graphs=None, returns_graph=True)
647def degree_sequence_tree(deg_sequence, create_using=None):
648 """Return a tree with the given degree sequence.
650 Two conditions must be met for a degree sequence to be valid for a tree:
652 1. The number of nodes must be one more than the number of edges.
653 2. The degree sequence must be trivial or have only strictly positive
654 node degrees.
656 Parameters
657 ----------
658 degree_sequence : iterable
659 Iterable of node degrees.
661 create_using : NetworkX graph constructor, optional (default=nx.Graph)
662 Graph type to create. If graph instance, then cleared before populated.
664 Returns
665 -------
666 networkx.Graph
667 A tree with the given degree sequence.
669 Raises
670 ------
671 NetworkXError
672 If the degree sequence is not valid for a tree.
674 If `create_using` is directed.
676 See Also
677 --------
678 random_degree_sequence_graph
679 """
680 deg_sequence = list(deg_sequence)
681 valid, reason = nx.utils.is_valid_tree_degree_sequence(deg_sequence)
682 if not valid:
683 raise nx.NetworkXError(reason)
685 G = nx.empty_graph(0, create_using)
686 if G.is_directed():
687 raise nx.NetworkXError("Directed Graph not supported")
689 if deg_sequence == [0]:
690 G.add_node(0)
691 return G
693 # Sort all degrees greater than 1 in decreasing order.
694 #
695 # TODO Does this need to be sorted in reverse order?
696 deg = sorted((s for s in deg_sequence if s > 1), reverse=True)
698 # make path graph as backbone
699 n = len(deg) + 2
700 nx.add_path(G, range(n))
701 last = n
703 # add the leaves
704 for source in range(1, n - 1):
705 nedges = deg.pop() - 2
706 G.add_edges_from((source, target) for target in range(last, last + nedges))
707 last += nedges
708 return G
711@py_random_state(1)
712@nx._dispatchable(graphs=None, returns_graph=True)
713def random_degree_sequence_graph(sequence, seed=None, tries=10):
714 r"""Returns a simple random graph with the given degree sequence.
716 If the maximum degree $d_m$ in the sequence is $O(m^{1/4})$ then the
717 algorithm produces almost uniform random graphs in $O(m d_m)$ time
718 where $m$ is the number of edges.
720 Parameters
721 ----------
722 sequence : list of integers
723 Sequence of degrees
724 seed : integer, random_state, or None (default)
725 Indicator of random number generation state.
726 See :ref:`Randomness<randomness>`.
727 tries : int, optional
728 Maximum number of tries to create a graph
730 Returns
731 -------
732 G : Graph
733 A graph with the specified degree sequence.
734 Nodes are labeled starting at 0 with an index
735 corresponding to the position in the sequence.
737 Raises
738 ------
739 NetworkXUnfeasible
740 If the degree sequence is not graphical.
741 NetworkXError
742 If a graph is not produced in specified number of tries
744 See Also
745 --------
746 is_graphical, configuration_model
748 Notes
749 -----
750 The generator algorithm [1]_ is not guaranteed to produce a graph.
752 References
753 ----------
754 .. [1] Moshen Bayati, Jeong Han Kim, and Amin Saberi,
755 A sequential algorithm for generating random graphs.
756 Algorithmica, Volume 58, Number 4, 860-910,
757 DOI: 10.1007/s00453-009-9340-1
759 Examples
760 --------
761 >>> sequence = [1, 2, 2, 3]
762 >>> G = nx.random_degree_sequence_graph(sequence, seed=42)
763 >>> sorted(d for n, d in G.degree())
764 [1, 2, 2, 3]
765 """
766 DSRG = DegreeSequenceRandomGraph(sequence, seed)
767 for try_n in range(tries):
768 try:
769 return DSRG.generate()
770 except nx.NetworkXUnfeasible:
771 pass
772 raise nx.NetworkXError(f"failed to generate graph in {tries} tries")
775class DegreeSequenceRandomGraph:
776 # class to generate random graphs with a given degree sequence
777 # use random_degree_sequence_graph()
778 def __init__(self, degree, rng):
779 self.rng = rng
780 self.degree = list(degree)
781 if not nx.is_graphical(self.degree):
782 raise nx.NetworkXUnfeasible("degree sequence is not graphical")
783 # node labels are integers 0,...,n-1
784 self.m = sum(self.degree) / 2.0 # number of edges
785 try:
786 self.dmax = max(self.degree) # maximum degree
787 except ValueError:
788 self.dmax = 0
790 def generate(self):
791 # remaining_degree is mapping from int->remaining degree
792 self.remaining_degree = dict(enumerate(self.degree))
793 # add all nodes to make sure we get isolated nodes
794 self.graph = nx.Graph()
795 self.graph.add_nodes_from(self.remaining_degree)
796 # remove zero degree nodes
797 for n, d in list(self.remaining_degree.items()):
798 if d == 0:
799 del self.remaining_degree[n]
800 if len(self.remaining_degree) > 0:
801 # build graph in three phases according to how many unmatched edges
802 self.phase1()
803 self.phase2()
804 self.phase3()
805 return self.graph
807 def update_remaining(self, u, v, aux_graph=None):
808 # decrement remaining nodes, modify auxiliary graph if in phase3
809 if aux_graph is not None:
810 # remove edges from auxiliary graph
811 aux_graph.remove_edge(u, v)
812 if self.remaining_degree[u] == 1:
813 del self.remaining_degree[u]
814 if aux_graph is not None:
815 aux_graph.remove_node(u)
816 else:
817 self.remaining_degree[u] -= 1
818 if self.remaining_degree[v] == 1:
819 del self.remaining_degree[v]
820 if aux_graph is not None:
821 aux_graph.remove_node(v)
822 else:
823 self.remaining_degree[v] -= 1
825 def p(self, u, v):
826 # degree probability
827 return 1 - self.degree[u] * self.degree[v] / (4.0 * self.m)
829 def q(self, u, v):
830 # remaining degree probability
831 norm = max(self.remaining_degree.values()) ** 2
832 return self.remaining_degree[u] * self.remaining_degree[v] / norm
834 def suitable_edge(self):
835 """Returns True if and only if an arbitrary remaining node can
836 potentially be joined with some other remaining node.
838 """
839 nodes = iter(self.remaining_degree)
840 u = next(nodes)
841 return any(v not in self.graph[u] for v in nodes)
843 def phase1(self):
844 # choose node pairs from (degree) weighted distribution
845 rem_deg = self.remaining_degree
846 while sum(rem_deg.values()) >= 2 * self.dmax**2:
847 u, v = sorted(random_weighted_sample(rem_deg, 2, self.rng))
848 if self.graph.has_edge(u, v):
849 continue
850 if self.rng.random() < self.p(u, v): # accept edge
851 self.graph.add_edge(u, v)
852 self.update_remaining(u, v)
854 def phase2(self):
855 # choose remaining nodes uniformly at random and use rejection sampling
856 remaining_deg = self.remaining_degree
857 rng = self.rng
858 while len(remaining_deg) >= 2 * self.dmax:
859 while True:
860 u, v = sorted(rng.sample(list(remaining_deg.keys()), 2))
861 if self.graph.has_edge(u, v):
862 continue
863 if rng.random() < self.q(u, v):
864 break
865 if rng.random() < self.p(u, v): # accept edge
866 self.graph.add_edge(u, v)
867 self.update_remaining(u, v)
869 def phase3(self):
870 # build potential remaining edges and choose with rejection sampling
871 potential_edges = combinations(self.remaining_degree, 2)
872 # build auxiliary graph of potential edges not already in graph
873 H = nx.Graph(
874 [(u, v) for (u, v) in potential_edges if not self.graph.has_edge(u, v)]
875 )
876 rng = self.rng
877 while self.remaining_degree:
878 if not self.suitable_edge():
879 raise nx.NetworkXUnfeasible("no suitable edges left")
880 while True:
881 u, v = sorted(rng.choice(list(H.edges())))
882 if rng.random() < self.q(u, v):
883 break
884 if rng.random() < self.p(u, v): # accept edge
885 self.graph.add_edge(u, v)
886 self.update_remaining(u, v, aux_graph=H)