Generate scale-free networks with power-law degree distributions using Barabasi-Albert

Problem Detail: 

I'm trying to reproduce the synthetic networks (graphs) described in some papers.

It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree distributions, $P_A(k) ∝ k^{-λ}$".

$P_A$ is a probability distribution that returns the number of nodes with degree $k$. For instance, $P_A(2)$ is the number of nodes with degree 2.

The average degree $k$ stroke seems to be 4 in one paper, with a the minimum $k$ of 2. No word about the maximum $k$. In the other paper it is not specified. It does not seem that important to define the network.

Lambda λ values are given, as is the number of nodes $n$. Combinations are

1. n = 50000, λ = 3, 2.7, 2.3, with in a paper
2. n = 4000 and λ = 2.5, or n = 6000 and λ = 3 in the other paper

I looked for libraries implementing the Barabasi-Albert algorithm and they seem to require different parameters than lambda and the average degree. One is NetworkX, another is GraphStream (implementation here). They work in similar ways and ask for:

• n : int - number of nodes
• m : int - number of edges to attach from a new node to existing nodes; the number of edges to be added at each step

How can I calculate the settings m to generate a comparable graph?

Here are some references:

• Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
• Small Cluster in Cyber Physical Systems, Huang et al. 2014
• Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used "generating functions" to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

Thanks.

Asked By : Agostino

Answered By : Fizz

The short answer is that you can't use that software as-is to get what you want. For a fixed $m$, the Barabasi-Albert model always has the degree distribution $P_k \sim k^{-3}$, regardless of $m$. The exact formula for the probability degree of what those pieces of software implement (which is the BA model) is

$$ P_k = \frac{2m(m+1)}{k(k+1)(k+2)}$$

The papers (with $\lambda \neq 3$) are probably talking about some kind of generalized BA model, I presume. It would help to give more details (full citations) on them.

EDIT: OK, I'll have at look at those refs. In the meantime, I've discovered there's R package called igraph that can do what you want. The relevant theory paper/cited used there is:

• "Connected Components in Random Graphs with Given Expected Degree Sequences" by Fan Chung, Linyuan Lu.

It has some 400 citations in Google Scholar, so it's probably a widely used method. The later, 2009 paper cited on that R package page clearly says "SF networks contain heterogeneous degrees, and their distribution follows a power law, $P_d(k) \sim k^{-\lambda}$. To construct artificial SF networks, a stochastic model called the Chung and Lu (CL) model is used."

EDIT2: I think you have misread Huang et al. "We build synthetic random, scale-free and small-world networks using Erdos-Renyi model, Barabasi-Albert model and Watts and Strogatz model [9] respectively." It doesn't say anywhere they got BA to do any power other than 3. There's a figure caption which says "We use 'k-n' interdependence model to couple two synthetic scale-free networks $G_p$ and $G_c$ with the power law exponents 2.5 and 3 respectively." But that doesn't mean they used BA for those 2.5-degree graphs. There's one later figure which only says "Barabasi-Albert model is used to generate scale-free network with power law exponent 3."

EDIT3: The paper by Buldyrev et al. doesn't say anywhere they've used any BA graphs. "Simulation results for P8 as a function of p for for SF networks with $\lambda$ = 3, 2.7, 2.3". They don't say how they got those graphs. The do cite the BA papers, but only in long list of 10 papers about various random network models. The second paper of this group by Havlin et al. does indeed give on p. 5 the BA model as having an indeterminate/unspecified $\lambda$, citing the 1999 BA paper. I don't really want to call this paper wrong, but the only correct reading of it is $\lambda = 3$. Again it doesn't say how they generated their $\lambda = 2.7$ graphs from their Fig 8. I can see how reading this paper you can conclude that BA can generate such graphs... but it can't.

EDIT4: Yes, I found it now in the actual version published in Nature "For two interdependent scale-free networks² with power-law degree distributions, $P_A(k) \sim P_B(k) / k^{-\lambda}$, we find that the existence criteria for the giant component are quite different from those in a single network." The citation is indeed misleading in the same way as in the Halvin et al., but they don't say they've used the BA process to generate the graphs. The passage can be interpreted as only a citing BA 1999 reference for what scale-free network means and/or who originated the concept. In any case, trust the math... you can find the derivation for the BA degree formula in numerous places, including BA's own paper or in more detail in a later book[let]. BA obviously understood the generality of what they observed, so they stated a law that is more general (arbitrary $\lambda$) than what their construction provides, i.e. $\lambda = 3$. As I said before, there are other methods (subsequently published by others, e.g. Chung and Lu) to get a different $\lambda$, but they are not using the BA construction, even though their graphs are correctly called scale-free too.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39764