Home | Trees | Indices | Help |
---|
|
Author: Aric Hagberg (hagberg@lanl.gov) Pieter Swart (swart@lanl.gov) Dan Schult (dschult@colgate.edu)
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|
Return a random pseudograph with the given degree sequence.
>>> 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:
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}, }
|
Return a simple graph with given degree sequence, constructed using the Havel-Hakimi algorithm.
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:
|
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.
See Theorem 1.4 in [chartrand-graphs-1996]. This algorithm is also used in havel_hakimi_graph() References:
|
Attempt to create a valid degree sequence of length n using specified function sfunction(n,**kwds).
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.
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} } |
Home | Trees | Indices | Help |
---|
Generated by Epydoc 3.0beta1 on Sun Aug 17 12:04:44 2008 | http://epydoc.sourceforge.net |