881 views

Skip to first unread message

May 11, 2017, 6:46:00 AM5/11/17

to networkx-discuss

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.

May 11, 2017, 6:51:42 AM5/11/17

to networkx...@googlegroups.com

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.

May 11, 2017, 10:02:07 AM5/11/17

to networkx-discuss

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 ×

mtimes on each random network, wheremis 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.

May 17, 2017, 5:17:14 AM5/17/17

to networkx-discuss

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?

May 17, 2017, 5:35:05 AM5/17/17

to networkx...@googlegroups.com

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.

May 17, 2017, 6:30:35 AM5/17/17

to networkx...@googlegroups.com

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

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.

May 17, 2017, 9:36:02 AM5/17/17

to networkx-discuss

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.`

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.

May 17, 2017, 9:50:37 AM5/17/17

to networkx...@googlegroups.com

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

May 17, 2017, 12:06:17 PM5/17/17

to networkx-discuss

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.

May 25, 2017, 8:08:04 AM5/25/17

to networkx-discuss

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.

May 6, 2022, 8:05:42 AMMay 6

to networkx-discuss

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

May 6, 2022, 9:11:16 AMMay 6

to networkx...@googlegroups.com

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu