Package networkx :: Package generators :: Module degree_seq
[frames | no frames]

Module networkx.generators.degree_seq

Generate graphs with a given degree sequence.


Function Summary
  configuration_model(deg_sequence, seed)
Return a pseudograph with given degree sequence.
  create_degree_sequence(n, sfunction, max_tries, **kwds)
Attempt to create a valid degree sequence of length n using specified function sfunction(n,kwds).
  degree_sequence_tree(deg_sequence)
Make a tree for the given degree sequence.
  havel_hakimi_graph(deg_sequence, seed)
Return a simple graph with given degree sequence, constructed using the Havel-Hakimi algorithm.
  is_valid_degree_sequence(deg_sequence)
Return True if deg_sequence is a valid sequence of integer degrees equal to the degree sequence of some simple graph.

Variable Summary
str __author__ = 'Aric Hagberg (hagberg@lanl.gov)\nPieter Sw...
str __credits__ = ''
str __date__ = '$Date: 2005-06-15 12:42:59 -0600 (Wed, 15 Ju...
str __revision__ = '$Revision: 1037 $'

Function Details

configuration_model(deg_sequence, seed=None)

Return a pseudograph with given degree sequence.

  • deg_sequence: degree sequence, a list of integers with each entry

    corresponding to the degree of a node (need not be sorted). A non-graphical degree sequence (i.e. one not realizable by some simple graph) will raise an Exception.

  • seed: seed for random number generator (default=None)

Steps:
  • Check if deg_sequence is a valid degree sequence.
  • Create N nodes with stubs of given degree.
  • Randomly select two available stubs and connect them with an edge.

As described by Newman [newman-2003-structure].

Nodes are labeled 1,.., len(deg_sequence), corresponding to their position in deg_sequence.

This process can lead to duplicate edges and loops, and therefore returns a pseudograph type. You can call remove_parallel() and remove_selfloops() to get a simple graph (but likely without the exact specified degree sequence). This "finite-size effect" decreases as the size of the graph increases.

References:

[newman-2003-structure] M.E.J. Newman, "The structure and function of complex networks", SIAM REVIEW 45-2, pp 167-256, 2003.

create_degree_sequence(n, sfunction=None, max_tries=50, **kwds)

Attempt to create a valid degree sequence of length n using specified function sfunction(n,kwds).

  • n: length of degree sequence = number of nodes

  • sfunction: a function, called as "sfunction(n,kwds)",

    that returns a list of n real or integer values.

  • max_tries: max number of attempts at creating valid degree

    sequence.

Repeatedly create a degree sequence by calling sfunction(n,kwds) until achieving a valid degree sequence. If unsuccessful after max_tries attempts, raise an exception.

For examples of sfunctions that return sequences of random numbers, see networkx.Utils.

>>> from networkx.utils import *
>>> seq=create_degree_sequence(10,uniform_sequence)

degree_sequence_tree(deg_sequence)

Make a tree for the given degree sequence.

A tree has #nodes-#edges=1 so the degree sequence must have len(deg_sequence)-sum(deg_sequence)/2=1

havel_hakimi_graph(deg_sequence, seed=None)

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

  • deg_sequence: degree sequence, a list of integers with each entry

    corresponding to the degree of a node (need not be sorted). A non-graphical degree sequence (not sorted). A non-graphical degree sequence (i.e. one not realizable by some simple graph) raises an Exception.

  • seed: seed for random number generator (default=None)

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.

See Theorem 1.4 in [chartrand-graphs-1996]. This algorithm is also used in the function is_valid_degree_sequence.

References:

[chartrand-graphs-1996] G. Chartrand and L. Lesniak, "Graphs and Digraphs",
Chapman and Hall/CRC, 1996.

is_valid_degree_sequence(deg_sequence)

Return True if deg_sequence is a valid sequence of integer degrees equal to the degree sequence of some simple graph.

  • deg_sequence: degree sequence, a list of integers with each entry

    corresponding to the degree of a node (need not be sorted). A non-graphical degree sequence (i.e. one not realizable by some simple graph) will raise an exception.

See Theorem 1.4 in [chartrand-graphs-1996]. This algorithm is also used in havel_hakimi_graph()

References:

[chartrand-graphs-1996] G. Chartrand and L. Lesniak, "Graphs and Digraphs",
Chapman and Hall/CRC, 1996.

Variable Details

__author__

Type:
str
Value:
'''Aric Hagberg (hagberg@lanl.gov)
Pieter Swart (swart@lanl.gov)
Dan Schult (dschult@colgate.edu)'''                                    

__credits__

Type:
str
Value:
''                                                                     

__date__

Type:
str
Value:
'$Date: 2005-06-15 12:42:59 -0600 (Wed, 15 Jun 2005) $'                

__revision__

Type:
str
Value:
'$Revision: 1037 $'                                                    

Generated by Epydoc 2.1 on Sun Aug 21 08:06:58 2005 http://epydoc.sf.net