CODEWITHSUNDEEP
pythongraphstatisticsnetworkx
Null_Space
Null_Space

Reputation: 469

Generate a power-law degree distribution in python

Let n be the size of the network, and t be the power-law exponent. The goal is to generate a random graph G of n vertices with a power-law degree distribution specified by t.

There are several existing answers: (1) answer 1 and (2) answer 2, which all use random.paretovariate() function. However, this is no guarantee that the resulting sequence is a valid degree sequence.

I also checked networkx and failed to find any function that produces a power-law degree sequence. Is there a way to do this in Python?

Upvotes: 2

Views: 1590

Answers (1)

user16329476
user16329476

Reputation:

You can do this using networkx. The is_graphical function allows you to determine whether the results of the powerlaw_sequence function are a valid degree sequence. Once we generate a valid sequence, we can create a random graph from it.


    from networkx.generators.degree_seq import random_degree_sequence_graph
    from networkx.algorithms.graphical import is_graphical
    from networkx.utils.random_sequence import powerlaw_sequence
    
    
    n, t = 10, 2
    while True:  # Continue generating sequences until one of them is graphical
        seq = sorted([int(round(d)) for d in powerlaw_sequence(n, t)], reverse=True)  # Round to nearest integer to obtain DISCRETE degree sequence
        if is_graphical(seq):
            break
    G = random_degree_sequence_graph(seq, tries=100)  # Adjust number of tries as you see fit
    print(sorted(d for _, d in G.degree()))

Upvotes: 1

Related Questions