pythonalgorithmrgraphnetworkx

Generating a graph with certain degree distribution?


I am trying to generate a random graph that has small-world properties (exhibits a power law distribution). I just started using the networkx package and discovered that it offers a variety of random graph generation. Can someone tell me if it possible to generate a graph where a given node's degree follows a gamma distribution (either in R or using python's networkx package)?


Solution

  • If you want to use the configuration model something like this should work in NetworkX:

    import random 
    import networkx as nx
    z=[int(random.gammavariate(alpha=9.0,beta=2.0)) for i in range(100)]
    G=nx.configuration_model(z)
    

    You might need to adjust the mean of the sequence z depending on parameters in the gamma distribution. Also z doesn't need to be graphical (you'll get a multigraph), but it does need an even sum so you might have to try a few random sequences (or add 1)...

    The NetworkX documentation notes for configuration_model give another example, a reference and how to remove parallel edges and self loops:

    Notes
    -----
    As described by Newman [1]_.
    
    A non-graphical degree sequence (not realizable by some simple
    graph) is allowed since this function returns graphs with self
    loops and parallel edges.  An exception is raised if the degree
    sequence does not have an even sum.
    
    This configuration model construction process can lead to
    duplicate edges and loops.  You can remove the self-loops and
    parallel edges (see below) which will likely result in a graph
    that doesn't have the exact degree sequence specified.  This
    "finite-size effect" decreases as the size of the graph increases.
    
    References
    ----------
    .. [1] M.E.J. Newman, "The structure and function
           of complex networks", SIAM REVIEW 45-2, pp 167-256, 2003.
    
    Examples
    --------
    >>> from networkx.utils import powerlaw_sequence
    >>> z=nx.create_degree_sequence(100,powerlaw_sequence)
    >>> G=nx.configuration_model(z)
    
    To remove parallel edges:
    
    >>> G=nx.Graph(G)
    
    To remove self loops:
    
    >>> G.remove_edges_from(G.selfloop_edges())
    

    Here is an example similar to the one at http://networkx.lanl.gov/examples/drawing/degree_histogram.html that makes a drawing including a graph layout of the largest connected component:

    #!/usr/bin/env python
    import random
    import matplotlib.pyplot as plt
    import networkx as nx
    
    def seq(n):
        return [random.gammavariate(alpha=2.0,beta=1.0) for i in range(100)]    
    z=nx.create_degree_sequence(100,seq)
    nx.is_valid_degree_sequence(z)
    G=nx.configuration_model(z)  # configuration model
    
    degree_sequence=sorted(nx.degree(G).values(),reverse=True) # degree sequence
    print "Degree sequence", degree_sequence
    dmax=max(degree_sequence)
    
    plt.hist(degree_sequence,bins=dmax)
    plt.title("Degree histogram")
    plt.ylabel("count")
    plt.xlabel("degree")
    
    # draw graph in inset 
    plt.axes([0.45,0.45,0.45,0.45])
    Gcc=nx.connected_component_subgraphs(G)[0]
    pos=nx.spring_layout(Gcc)
    plt.axis('off')
    nx.draw_networkx_nodes(Gcc,pos,node_size=20)
    nx.draw_networkx_edges(Gcc,pos,alpha=0.4)
    
    plt.savefig("degree_histogram.png")
    plt.show()