Logo Search packages:      
Sourcecode: python-networkx version File versions  Download package

def networkx::generators::degree_seq::configuration_model (   deg_sequence,
  seed = None 
)

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.
    

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 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.
        
    """
    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 N-node 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 degree-repeated 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[n-1]):
            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):


Generated by  Doxygen 1.6.0   Back to index