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

Module degree_seq

source code

Generate graphs with a given degree sequence or expected degree sequence.


Author: Aric Hagberg (hagberg@lanl.gov) Pieter Swart (swart@lanl.gov) Dan Schult (dschult@colgate.edu)

Functions [hide private]
 
configuration_model(deg_sequence, seed=None)
Return a random pseudograph with the given degree sequence.
source code
 
expected_degree_graph(w, seed=None)
Return a random graph G(w) with expected degrees given by w.
source code
 
havel_hakimi_graph(deg_sequence)
Return a simple graph with given degree sequence, constructed using the Havel-Hakimi algorithm.
source code
 
degree_sequence_tree(deg_sequence)
Make a tree for the given degree sequence.
source code
 
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.
source code
 
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).
source code
 
double_edge_swap(G, nswap=1)
Attempt nswap double-edge swaps on the graph G.
source code
 
connected_double_edge_swap(G, nswap=1)
Attempt nswap double-edge swaps on the graph G.
source code
 
li_smax_graph(degree_seq)
Generates a graph based with a given degree sequence and maximizing the s-metric.
source code
 
connected_smax_graph(degree_seq)
Not implemented.
source code
 
s_metric(G)
Return the "s-Metric" of graph G: the sum of the product deg(u)*deg(v) for every edge u-v in G
source code
 
_test_suite() source code
Function Details [hide private]

configuration_model(deg_sequence, seed=None)

source code 

Return a random pseudograph with the 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)

>>> z=create_degree_sequence(100,powerlaw_sequence)
>>> G=configuration_model(z)

The pseudograph G is a networkx.XGraph that allows multiple (parallel) edges between nodes and edges that connect nodes to themseves (self loops).

To remove self-loops:

>>> G.ban_selfloops()

To remove parallel edges:

>>> G.ban_multiedges()

Steps:

  • Check if deg_sequence is a valid degree sequence.
  • Create N nodes with stubs for attaching edges
  • 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 remove the self-loops and parallel edges (see above) with the likely result of not getting the exat degree sequence specified. 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.

expected_degree_graph(w, seed=None)

source code 

Return a random graph G(w) with expected degrees given by w.

>>> z=[10 for i in range(100)]
>>> G=expected_degree_graph(z)

To remove self-loops:

>>> G.ban_selfloops()

Reference:

@Article{connected-components-2002,
  author =        {Fan Chung and L. Lu},
  title =         {Connected components in random graphs
  with given expected degree sequences},
  journal =       {Ann. Combinatorics},
  year =          {2002},
  volume =        {6},
  pages =         {125-145},
  }
Parameters:
  • w - a list of expected degrees
  • seed - seed for random number generator (default=None)

havel_hakimi_graph(deg_sequence)

source code 

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.

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.

degree_sequence_tree(deg_sequence)

source code 

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

is_valid_degree_sequence(deg_sequence)

source code 

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.

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

source code 

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)

double_edge_swap(G, nswap=1)

source code 

Attempt nswap double-edge swaps on the graph G.

Return count of successful swaps. The graph G is modified in place. A double-edge swap removes two randomly choseen edges u-v and x-y and creates the new edges u-x and v-y:

u--v            u  v
       becomes  |  |
x--y            x  y

If either the edge u-x or v-y already exist no swap is performed so the actual count of swapped edges is always <= nswap

Does not enforce any connectivity constraints.

connected_double_edge_swap(G, nswap=1)

source code 

Attempt nswap double-edge swaps on the graph G.

Returns count of successful swaps. Enforces connectivity. The graph G is modified in place.

A double-edge swap removes two randomly choseen edges u-v and x-y and creates the new edges u-x and v-y:

u--v            u  v
       becomes  |  |
x--y            x  y

If either the edge u-x or v-y already exist no swap is performed so the actual count of swapped edges is always <= nswap

The initial graph G must be connected and the resulting graph is connected.

Reference:

@misc{gkantsidis-03-markov,
 author = "C. Gkantsidis and M. Mihail and E. Zegura",
 title = "The Markov chain simulation method for generating connected
          power law random graphs",
 year = "2003",
 url = "http://citeseer.ist.psu.edu/gkantsidis03markov.html"
}

li_smax_graph(degree_seq)

source code 

Generates a graph based with a given degree sequence and maximizing the s-metric. Experimental implementation.

Maximum s-metrix means that high degree nodes are connected to high degree nodes.

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

    corresponding to the degree of a node. A non-graphical degree sequence raises an Exception.

Reference:

@unpublished{li-2005,
 author = {Lun Li and David Alderson and Reiko Tanaka
          and John C. Doyle and Walter Willinger},
 title = {Towards a Theory of Scale-Free Graphs:
         Definition, Properties, and  Implications (Extended Version)},
 url = {http://arxiv.org/abs/cond-mat/0501169},
 year = {2005}
}

The algorithm:

STEP 0 - Initialization
A = {0}
B = {1, 2, 3, ..., n}
O = {(i; j), ..., (k, l),...} where i < j, i <= k < l and
        d_i * d_j >= d_k *d_l
wA = d_1
dB = sum(degrees)

STEP 1 - Link selection
(a) If |O| = 0 TERMINATE. Return graph A.
(b) Select element(s) (i, j) in O having the largest d_i * d_j , if for
        any i or j either w_i = 0 or w_j = 0 delete (i, j) from O
(c) If there are no elements selected go to (a).
(d) Select the link (i, j) having the largest value w_i (where for each
        (i, j) w_i is the smaller of w_i and w_j ), and proceed to STEP 2.

STEP 2 - Link addition
Type 1: i in A and j in B.
        Add j to the graph A and remove it from the set B add a link
        (i, j) to the graph A. Update variables:
        wA = wA + d_j -2 and dB = dB - d_j
        Decrement w_i and w_j with one. Delete (i, j) from O
Type 2: i and j in A.
    Check Tree Condition: If dB = 2 * |B| - wA.
        Delete (i, j) from O, continue to STEP 3
    Check Disconnected Cluster Condition: If wA = 2.
        Delete (i, j) from O, continue to STEP 3
    Add the link (i, j) to the graph A
    Decrement w_i and w_j with one, and wA = wA -2
STEP 3
    Go to STEP 1

The article states that the algorithm will result in a maximal s-metric. This implementation can not guarantee such maximality. I may have misunderstood the algorithm, but I can not see how it can be anything but a heuristic. Please contact me at sundsdal@gmail.com if you can provide python code that can guarantee maximality. Several optimizations are included in this code and it may be hard to read. Commented code to come.

s_metric(G)

source code 

Return the "s-Metric" of graph G: the sum of the product deg(u)*deg(v) for every edge u-v in G

Reference:

@unpublished{li-2005,
 author = {Lun Li and David Alderson and
          John C. Doyle and Walter Willinger},
 title = {Towards a Theory of Scale-Free Graphs:
          Definition, Properties, and  Implications (Extended Version)},
 url = {http://arxiv.org/abs/cond-mat/0501169},
 year = {2005}
 }