Fast generation of random scale-free networks with a defined power law using R
1
0
Entering edit mode
7.5 years ago
kobipe3 ▴ 90

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

power-law scale-free network graph R • 4.5k views
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.

0
Entering edit mode

This is not the right forum for this question

0
Entering edit mode

A better place for this question is probably here.

1
Entering edit mode
7.5 years ago
kobipe3 ▴ 90

I have found an answer in StackOverflow here

0
Entering edit mode

Thanks for following up and posting the answer.