Biostar Beta. Not for public use.
Fast generation of random scale-free networks with a defined power law using R
0
Entering edit mode
5.3 years ago
kobipe3 • 80
Israel

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 permutating 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 it 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 Barabasi algorithm. However, I do not know if I can parameterize it to produce a graph obeying my specific power law.

Yours,

Kobi

ADD COMMENTlink
1
Entering edit mode

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. :-)

ADD REPLYlink
0
Entering edit mode

this is not the right forum for this question

ADD REPLYlink
0
Entering edit mode

A better place for this question is probably here: http://stats.stackexchange.com/

ADD REPLYlink
0
Entering edit mode
ADD COMMENTlink
0
Entering edit mode

thanks for following up and posting the answer.

ADD REPLYlink

Login before adding your answer.

Similar Posts
Loading Similar Posts
Powered by the version 2.3.1