Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.generators.degree_seq.directed_configuration_model

directed_configuration_model(in_degree_sequence, out_degree_sequence, create_using=None, seed=None)[source]

Returns a directed_random graph with the given degree sequences.

The configuration model generates a random directed pseudograph (graph with parallel edges and self loops) by randomly assigning edges to match the given degree sequences.

Parameters
  • in_degree_sequence (list of nonnegative integers) – Each list entry corresponds to the in-degree of a node.

  • out_degree_sequence (list of nonnegative integers) – Each list entry corresponds to the out-degree of a node.

  • create_using (NetworkX graph constructor, optional (default MultiDiGraph)) – Graph type to create. If graph instance, then cleared before populated.

  • seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.

Returns

G – A graph with the specified degree sequences. Nodes are labeled starting at 0 with an index corresponding to the position in deg_sequence.

Return type

MultiDiGraph

Raises

NetworkXError – If the degree sequences do not have the same sum.

Notes

Algorithm as described by Newman 1.

A non-graphical degree sequence (not realizable by some simple graph) is allowed since this function returns graphs with self loops and parallel edges. An exception is raised if the degree sequences does not have the same sum.

This configuration model construction process can lead to duplicate edges and loops. You can remove the self-loops and parallel edges (see below) which will likely result in a graph that doesn’t have the exact degree sequence specified. This “finite-size effect” decreases as the size of the graph increases.

References

1

Newman, M. E. J. and Strogatz, S. H. and Watts, D. J. Random graphs with arbitrary degree distributions and their applications Phys. Rev. E, 64, 026118 (2001)

Examples

One can modify the in- and out-degree sequences from an existing directed graph in order to create a new directed graph. For example, here we modify the directed path graph:

>>> D = nx.DiGraph([(0, 1), (1, 2), (2, 3)])
>>> din = list(d for n, d in D.in_degree())
>>> dout = list(d for n, d in D.out_degree())
>>> din.append(1)
>>> dout[0] = 2
>>> # We now expect an edge from node 0 to a new node, node 3.
... D = nx.directed_configuration_model(din, dout)

The returned graph is a directed multigraph, which may have parallel edges. To remove any parallel edges from the returned graph:

>>> D = nx.DiGraph(D)

Similarly, to remove self-loops:

>>> D.remove_edges_from(nx.selfloop_edges(D))