graphscope.nx.generators.degree_seq.havel_hakimi_graph#

graphscope.nx.generators.degree_seq.havel_hakimi_graph(deg_sequence, create_using=None)[source]#

Returns a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.

Parameters:
  • deg_sequence (list of integers) – Each integer corresponds to the degree of a node (need not be sorted).

  • create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated. Directed graphs are not allowed.

Raises:

NetworkXException – For a non-graphical degree sequence (i.e. one not realizable by some simple graph).

Notes

The Havel-Hakimi algorithm constructs a simple graph by successively connecting the node of highest degree to other nodes of highest degree, resorting remaining nodes by degree, and repeating the process. The resulting graph has a high degree-associativity. Nodes are labeled 1,.., len(deg_sequence), corresponding to their position in deg_sequence.

The basic algorithm is from Hakimi [1] and was generalized by Kleitman and Wang [2].

References