NetworkX

Previous topic

random_powerlaw_tree_sequence

Next topic

directed_configuration_model

configuration_model

configuration_model(deg_sequence, create_using=None, seed=None)[source]

Return a random graph with the given degree sequence.

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

Parameters :

deg_sequence : list of integers

Each list entry corresponds to the degree of a node.

create_using : graph, optional (default MultiGraph)

Return graph of this type. The instance will be cleared.

seed : hashable object, optional

Seed for random number generator.

Returns :

G : MultiGraph

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

Raises :

NetworkXError :

If the degree sequence does not have an even sum.

See also

is_valid_degree_sequence

Notes

As described by Newman [R189].

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 sequence does not have an even 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

[R189](1, 2) M.E.J. Newman, “The structure and function of complex networks”, SIAM REVIEW 45-2, pp 167-256, 2003.

Examples

>>> from networkx.utils import powerlaw_sequence
>>> z=nx.utils.create_degree_sequence(100,powerlaw_sequence)
>>> G=nx.configuration_model(z)

To remove parallel edges:

>>> G=nx.Graph(G)

To remove self loops:

>>> G.remove_edges_from(G.selfloop_edges())