Fast generation of random scale-free networks with a defined power law using R

Question

[kobipe3]

I wanted to permute graph edges in a degree perserving manner for my analysis.

The problem is that the graph is very large so using a simple rewire algorithm is very slow (~230,000 edges, ~7,000 nodes).

I know that the original graph I am permuting is scale-free and the power law is that frequency of node connectivity k is 0.4412k^(-1.223). The graph is undirected, and all the nodes within it have at least degree 1 (the graph is taken from http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3214599/).

I thought of generating graphs with similar degree distribution using some algorithm for creating scale-free networks, and to assign afterwards the node labels from the original graph according to the rank of the degrees in a sorted list.

I saw that the R package igraph have a very fast implementation of Barabási algorithm. However, I do not know if I can parameterize it to produce a graph obeying my specific power law.

Yours,
Kobi

[David Westergaard]

Honestly, a simple re-wire algorithm for that problem should not be that slow. The task can easily be split over multiple threads and you can just save the resulting random graph if you need it for later analysis.

Before concluding the network is scale-free please read http://arxiv.org/abs/0706.1062. Sumazin et al. uses a least-squares fit and concludes it comes from a power law distribution. Clauset et al. discusses why this is not a good test and details a more appropriate way of testing this.

Edit: I also just noticed you had already discovered this article. :-)

[Istvan Albert]

This is not the right forum for this question

[Ying W]

A better place for this question is probably here.

Answer 1

[kobipe3]

I have found an answer in StackOverflow here

[Istvan Albert]

Thanks for following up and posting the answer.