Random Network Generator using a network re-wiring approach?

[Tom]

Hi all, I have a network (edge_list) and I want to randomise it using this method:

"Random networks were generated using a network rewiring approach. Each random network was generated by repeatedly choosing two edges at random (e.g., A–B and C–D) and swapping them (yielding A–D and C–B, or A–C and B–D). This operation was iterated 100 × m times on each random network, where m is the number of edges. Therefore, each random network contains the same nodes, the same number of edges, and the same degree for each node as the original network. "

I can read in the graph that I want to randomise:

import networkx as nx
graph = nx.read_edgelist("ListOfGenesInNetwork.NonRedundant",delimiter="\t",nodetype=str)

But then I'm confused, is it possible to do the above network re-wiring approach using NetworkX?  I have seen random_graph_generator function in NetworkX, but I'm not sure that this is what I want...I'm just a bit confused as to where to start with the randomisation via network re-wiring step, if someone could point me in the right direction I'd appreciate it.

[Daniel Schult]

You have already "generated" your network, so you should look in the "algorithms" section of the docs to rewire it. In particular, the section on edge swaps.  In the top portion of those  doc pages is a green link to the python code in case you need to do something close to, but not the same as what these routines do.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Tom]

Thank you. Just posting the code I came up with, in case it helps anyone else.

What I wanted to do is: "Random networks were generated using a network rewiring approach. Each random network was generated by repeatedly choosing two edges at random (e.g., A–B and C–D) and swapping them (yielding A–D and C–B, or A–C and B–D). This operation was iterated 100 × m times on each random network, where m is the number of edges. Therefore, each random network contains the same nodes, the same number of edges, and the same degree for each node as the original network. "

What I did was:

import networkx as nx
import sys
graph = nx.read_edgelist(sys.argv[1],delimiter="\t",nodetype=str)
how_many_edges = int(len(graph.edges()))
how_many_times = int(len(graph.edges()))*100


 for i in range(1000):
    random_file = "random." + str(i) + ".txt"
    count = 0
    while count < how_many_times:
        random_network = nx.double_edge_swap(graph)
        count +=1
    nx.write_edgelist(random_network,random_file,delimiter="\t",data=False)

On Thursday, May 11, 2017 at 11:51:42 AM UTC+1, Daniel Schult wrote:

You have already "generated" your network, so you should look in the "algorithms" section of the docs to rewire it. In particular, the section on edge swaps.  In the top portion of those  doc pages is a green link to the python code in case you need to do something close to, but not the same as what these routines do.

On Thu, May 11, 2017 at 6:32 AM, Tom <dr.aoife.ma...@gmail.com> wrote:

Hi all, I have a network (edge_list) and I want to randomise it using this method:

"Random networks were generated using a network rewiring approach. Each random network was generated by repeatedly choosing two edges at random (e.g., A–B and C–D) and swapping them (yielding A–D and C–B, or A–C and B–D). This operation was iterated 100 × m times on each random network, where m is the number of edges. Therefore, each random network contains the same nodes, the same number of edges, and the same degree for each node as the original network. "

I can read in the graph that I want to randomise:

import networkx as nx
graph = nx.read_edgelist("ListOfGenesInNetwork.NonRedundant",delimiter="\t",nodetype=str)

But then I'm confused, is it possible to do the above network re-wiring approach using NetworkX?  I have seen random_graph_generator function in NetworkX, but I'm not sure that this is what I want...I'm just a bit confused as to where to start with the randomisation via network re-wiring step, if someone could point me in the right direction I'd appreciate it.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

[fee]

Hi all, this is a continuation of my previous question. As you can see from below/to refresh, I want to do this: "Random networks were generated using a network rewiring approach. Each random network was generated by repeatedly choosing two edges at random (e.g., A–B and C–D) and swapping them (yielding A–D and C–B, or A–C and B–D). This operation was iterated 100 × m times on each random network, where m is the number of edges. Therefore, each random network contains the same nodes, the same number of edges, and the same degree for each node as the original network"

The code I wrote is this (to make 100 random networks):

import networkx as nx
import sys
graph = nx.read_edgelist(sys.argv[1],delimiter="\t",nodetype=str)

how_many_times = int(len(graph.edges()))*100

for i in range(100):
    random_file = "random." + str(i) + ".txt"
    count = 0
    while count < how_many_times:
        random_network = nx.double_edge_swap(graph)
        count +=1
    nx.write_edgelist(random_network,random_file,delimiter="\t",data=False)

The problem is the code is prohibitively slow. When I run this on a test network with say 10 nodes, it works fine. However, my actual network has 220,000 edges (it is a protein interaction network of the whole genome). But so far, it hasn't even written one random network to file, in 121 hours. I've triple checked, this code definitely works on smaller sections of the data, so it's to do with the size of the file. I'm wondering if anyone can suggest a way of speeding up this script?

[Raf Guns]

Hi,

You are calling nx.double_edge_swap for each separate edge swap, which is not necessary. I think you can replace this part of your code:

    while count < how_many_times:
        random_network = nx.double_edge_swap(graph)
        count +=1



with this:

    nx.double_edge_swap(graph, nswap=how_many_times)



That will be much more efficient, although I suspect that this will still take a very long time on a graph with 220,000 edges.



Best,


Raf



To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.

[Daπid]

On 17 May 2017 at 11:17, fee <aoife.m...@gmail.com> wrote:

The problem is the code is prohibitively slow. When I run this on a test network with say 10 nodes, it works fine. However, my actual network has 220,000 edges (it is a protein interaction network of the whole genome). But so far, it hasn't even written one random network to file, in 121 hours. I've triple checked, this code definitely works on smaller sections of the data, so it's to do with the size of the file. I'm wondering if anyone can suggest a way of speeding up this script?

What you are doing is essentially equivalent to the configuration model.

https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.degree_seq.configuration_model.html

Instead of repeatedly rewire the network to randomise it, you build it at random from scratch. And this gives you stronger guarantees of the randomness, independently of the size.

[Tom]

Thanks for the replies; 

Raf, I did think of this, but unfortunately when I change the code to:

import networkx as nx
import sys
graph = nx.read_edgelist(sys.argv[1],delimiter="\t",nodetype=str)
how_many_times = int(len(graph.edges()))*100

for i in range(100):
    random_file = "random." + str(i) + ".txt"

    random_network = nx.double_edge_swap(graph,nswap=how_many_times)
    nx.write_edgelist(random_network,random_file,delimiter="\t",data=False)

I get the error:

  File "RandomiseNetwork.py", line 9, in <module>
    random_network = nx.double_edge_swap(graph,nswap=how_many_times)
  File "/home/nis/tom/env/local/lib/python2.7/site-packages/networkx-1.11rc2-py2.7.egg/networkx/algorithms/swap.py", line 66, in double_edge_swap
    raise nx.NetworkXError("Number of swaps > number of tries allowed.")

networkx.exception.NetworkXError: Number of swaps > number of tries allowed.

So that's why I did the workaround that I did. Although maybe I am mis-understanding something, is this saying that the number of swaps I want to do is too many? Or alternatively, maybe I am mis-understanding the error.

Daπid,

Thank you for your suggestion. I actually need to maintain the degree of each node in my random graphs (e.g. so if a node in the actual graph has 20 edges, it should have 20 edges in each random graph) (and the same number of nodes and edges), which I don't think the random configuration would give me?

Thanks for your help.

[Daπid]

On 17 May 2017 at 15:36, Tom <dr.aoife.ma...@gmail.com> wrote:

Thank you for your suggestion. I actually need to maintain the degree of each node in my random graphs (e.g. so if a node in the actual graph has 20 edges, it should have 20 edges in each random graph) (and the same number of nodes and edges), which I don't think the random configuration would give me?

That is exactly what the configuration model does. You first set every node with a fixed number of "stubs" (the degree), and then match pairs of them at random.

I think this is a better explanation than the reference in the docs: http://math.uchicago.edu/~shmuel/Network-course-readings/Random-Graphs-with-Arbitrary-Degree-Distributions-and-Their-Applications.pdf

[Tom]

Thank you for the reply.

I read through the paper and presented the idea to my supervisor. Unfortunately (for me, as I cannot figure this out!), he would like me to do the randomisation exactly as previously described (i.e. "Random networks were generated using a network rewiring approach. Each random network was generated by repeatedly choosing two edges at random (e.g., A–B and C–D) and swapping them (yielding A–D and C–B, or A–C and B–D). This operation was iterated 100 × m times on each random network, where m is the number of edges. Therefore, each random network contains the same nodes, the same number of edges, and the same degree for each node as the original network. ").

This is because we are using someone else's method on a new network, and so we need the results to be exactly comparable. For that reason, I've calculated centralities using the same software that they did (NetworkX) and now I need to randomise the data exactly as they did (as described above). However, maybe this is not possible, given that my network is bigger than theirs/the error that I am getting. I wonder if there is a way to not set a max on the number of swaps allowed (as this was my coding error, see earlier email).

Thanks.

[Tom]

I have come up with a solution (I think), I'm both posting it here in case it helps someone, and also to get feedback if possible:

I have a file of edges like this:

1   2
1   4
5   6
7   8
9   10

I want to randomise this network, maintaining the topology of the network; i.e. so if a node has a degree of 3 going into the randomisation, it will have a degree of 3 coming out of the randomisation:

The code:

import sys
import random
from datetime import datetime
startTime = datetime.now()

pair_lambda = lambda x: each_pair[x].split("_")
new_list_lambda = lambda x: pair1[x] + "_"+ pair2[x]
list_of_edges = [line.strip().split()[0] + "_" + line.strip().split()[1] for line in open(sys.argv[1])]
random.shuffle(list_of_edges)

for i in range(1000):
    random.shuffle(list_of_edges)
    paired_list = zip(list_of_edges,list_of_edges[1:])[::2]
    new_list = []
    for each_pair in paired_list:
        pair1,pair2 = pair_lambda(0),pair_lambda(1)
        new_list1,new_list2 = new_list_lambda(0),new_list_lambda(1)
        new_list.append(new_list1)
        new_list.append(new_list2)
    list_of_edges = new_list

print list_of_edges
print datetime.now() - startTime

If anyone has feedback I'd appreciate it.

[lukesky]

Hi Tom,

Chanced upon this discussion now. I have the same use case: I have given number of nodes, with degree sequence and I need to generate 1000 random graphs from this. I used networkxx configuration model, but my graph is huge : 20k nodes and 300,000,000 edges. Also in my case graph is a multi-graph with self-loops not allowed. So after I generate a graph using configuration model, I need to remove all self loops and start connecting random edges again from the intermediate graph. But this process is very slow and memory intensive. I was wondering once i get 1 random graph, how would I go about generating random graphs from this following maybe your approach of edge swapping ? since it might be faster?

Thanks

[Dan Schult]

You might take a look at double_edge_swap where the degree distribution stays the same but the edges trade nodes.