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