Module degree_seq

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.

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)

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.

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

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.

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)

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.

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"
}

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.

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}
 }