Keeping scale free graph's degree distribution after perturbation - python

Given a scale free graph G ( a graph whose degree distribution is a power law), and the following procedure:

for i in range(C):
    coint = randint(0,1)
    if (coint == 0):
        delete_random_edges(G)
    else:
        add_random_edge(G)

(C is a constant)
So, when C is large, the degree distribution after the procedure would be more like G(n,p). I am interested in preserving the power law distribution, i.e. - I want the graph to be scale free after this procedure, even for large C.

My idea is writing the procedures "delete_random_edges" and "add_random_edge" in a way that will give edges that connected to node with big degree small probability to be deleted (when adding new edge, it would be more likely to add it to node with large degree).

I use Networkx to represent the graph, and all I found is procedures that delete or add a specific edge. Any idea how can I implement the above?

Solution

Here's 2 algorithms:

Algorithm 1

This algorithm does not preserve the degree exactly, rather it preserves the expected degree.

Save each node's initial degree. Then delete edges at random. Whenever you create an edge, do so by randomly choosing two nodes, each with probability proportional to the initial degree of those nodes.

After a long period of time, the expected degree of each node 'u' is its initial degree (but it might be a bit higher or lower).

Basically, this will create what is called a Chung-Lu random graph. Networkx has a built in algorithm for creating them.

Note - this will allow the degree distribution to vary.

algorithm 1a

Here is the efficient networkx implementation skipping over the degree deleting and adding and going straight to the final result (assuming a networkx graph G):

degree_list = G.degree().values()
H = nx.expected_degree_graph(degree_list)

Here's the documentation

Algorithm 2

This algorithm preserves the degrees exactly.

Choose a set of edges and break them. Create a list, with each node appearing equal to the number of broken edges it was in. Shuffle this list. Create new edges between nodes that appear next to each other in this list.

Check to make sure you never join a node to itself or to a node which is already a neighbor. If this would occur you'll want to think of a custom way to avoid it. One option is to simply reshuffle the list. Another is to set those nodes aside and include them in the list you create next time you do this.

edit There is a built in networkx command double_edge_swapto swap two edges at a time. documentation