Question: Fast generation of random scale-free networks with a defined power law using R
0
gravatar for kobipe3
4.9 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

ADD COMMENTlink modified 4.9 years ago • written 4.9 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. 

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

ADD REPLYlink modified 4.9 years ago • written 4.9 years ago by David Westergaard1.4k

this is not the right forum for this question

ADD REPLYlink written 4.9 years ago by Istvan Albert ♦♦ 81k

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

ADD REPLYlink written 4.9 years ago by Ying W3.9k
0
gravatar for kobipe3
4.9 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

ADD COMMENTlink written 4.9 years ago by kobipe380

thanks for following up and posting the answer.

ADD REPLYlink written 4.9 years ago by Istvan Albert ♦♦ 81k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1151 users visited in the last hour