Question: Fast generation of random scale-free networks with a defined power law using R
0
5.8 years ago by
kobipe380
Israel
kobipe380 wrote:

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

Yours,

Kobi

modified 5.8 years ago • written 5.8 years ago by kobipe380
1

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.

this is not the right forum for this question

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

0
5.8 years ago by
kobipe380
Israel
kobipe380 wrote:

I have found an answer in here: http://stackoverflow.com/questions/26926403/create-random-graph-with-same-power-law-degree-distribution