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 nongraphical 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 selfloops: >>> 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 [newman2003structure]. 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 selfloops and parallel edges (see above) with the likely result of not getting the exat degree sequence specified. This "finitesize effect" decreases as the size of the graph increases. References: [newman2003structure] M.E.J. Newman, "The structure and function of complex networks", SIAM REVIEW 452, pp 167256, 2003. Definition at line 23 of file degree_seq.py. 00023 : """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 nongraphical 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 selfloops: >>> 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 [newman2003structure]. 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 selfloops and parallel edges (see above) with the likely result of not getting the exat degree sequence specified. This "finitesize effect" decreases as the size of the graph increases. References: [newman2003structure] M.E.J. Newman, "The structure and function of complex networks", SIAM REVIEW 452, pp 167256, 2003. """ if not is_valid_degree_sequence(deg_sequence): raise networkx.NetworkXError, 'Invalid degree sequence' if not seed is None: random.seed(seed) # start with empty Nnode graph N=len(deg_sequence) # G=networkx.empty_graph(N,create_using=networkx.Graph()) # no multiedges or selfloops # allow multiedges and selfloops G=networkx.empty_graph(N,create_using=networkx.XGraph(multiedges=True, \ selfloops=True)) if N==0 or max(deg_sequence)==0: # done if no edges return G # build stublist, a list of available degreerepeated stubs # e.g. for deg_sequence=[3,2,1,1,1] # initially, stublist=[1,1,1,2,2,3,4,5] # i.e., node 1 has degree=3 and is repeated 3 times, etc. stublist=[] for n in G: for i in range(deg_sequence[n1]): stublist.append(n) # while there are stubs in the sublist, randomly select two stubs, # connect them to make an edge, then pop them from the stublist while stublist: source=random.choice(stublist) stublist.remove(source) target=random.choice(stublist) stublist.remove(target) G.add_edge(source,target) G.name="configuration_model %d nodes %d edges"%(G.order(),G.size()) return G def expected_degree_graph(w, seed=None):
