pvalue calculation of protein-protein network with permutation test Note: this question has also been asked on Biostars

I have performed a network recreation analysis based on the interactions of proteins from String db.

I wanted to know if the interactions have significance by reshuffling the proteins with permutation against the background network. Since, its first time for me to perform permutation test on PPI, Can someone guide me to a tool or a tutorial to perform permutation test on newly created PPI network.

I tried looking at a youtube tutorial and read some articles like this one, but they were not very useful for my purpose.
It is probably necessary to correct for the degree distribution of the network, I am not sure that a tool such as the Mantel test will quite do this (as suggested by user Michael G.). In naturally occurring networks degree distribution is a strong confounder.

Then again I am not totally sure what shape your data is in or what the question is. You mention a background network, but I am not sure what this is or how you want to use it. Possibly your network reconstruction is a subset of your background network? In which case you just define the rule for how your subsample is drawn and then you compare it to permuted networks. 

However, here is some fairly crude but serviceable R code that implements a general purpose network rewiring test, using igraph. I am not using a background network as again I'm not sure what it is. 

(Python also has igraph so should be similar rewire() function)

compute_measure = function(network) {
  # i don't know what you are measuring, so you have to write this function.
  # this function takes a graph object as input 
  # this function returns a single numeric value (whatever you're measuring) as output
}

# "net" is a network of the graph type from igraph

measure = compute_measure(net)

num_perms = 1000

perm_measures = c()

for (i in 1:num_perms) {
  # permute the network by rewiring, rewire 10x as many times as edges
  # to ensure saturation
  perm_net = rewire(net, with = keeping_degseq(niter = gsize(net) * 10))
  perm_measures[i] = compute_measure(perm_net)
}

# one-sided monte carlo p value is proportion of rewirings (plus one) greater than your measure
p_value = (1 + length(which(perm_measures &gt;= measure))) / num_perms


If on the other hand you are just trying to come up with a single permutation of the edges of your network to compare against, you can run rewire() only once to get that permuted network. It depends on what question you are trying to answer, and what null hypothesis you're trying to get a p value for.