Search code examples
networkx

How to generate a random network graph based on degrees AND network density in NetworkX


There are a number of functions in NetworkX which allow for different types of random graphs to be generated.

Are there any which allow for the specified degree of the nodes as well as the overall network density (or similar metric) to be considered?


Solution

  • There may be other metrics that are possible to specify in the creation of a graph, but for your examples of degree and density, there exists only one combination of node and edge numbers that can meet specified degree an density criteria.

    For an undirected graph, the density is calculated as 2*m/(n*(n-1)) where m is the number of edges and n is the number of nodes. The average degree is calculated as 2*m/n.

    Using a bit of substitution, we can then say that n = (degree/density) + 1 and m = (n*degree)/2.

    With NetworkX, you can use nx.gnm_random_graph() to specify the number of nodes and edges to match those calculated above.

    If you use nx.gnp_random_graph(), note that the p parameter is equal to the density of the graph. Density is defined as the number of edges divided by the maximum number of possible edges, so including a probability that a node will attach to any of the other nodes (p) in generating the random graph effectively does the same thing. The resulting number of expected edges and average degree can then be easily calculated using that value and the number of nodes.