Help with Barabasi-Albert Model

[dholbach]

Hey folks! This is my first post and I am very happy to be here. I hope to contribute a lot, especially to the mathematics, physics, amateur science, and philosophy sections.

I am trying to write a program, in C++, to replicate the Barabasi-Albert algorithm for generating scale-free networks (i.e. networks whose degree distribution is power-law distributed). In order to check whether the algorithm was correct, I plotted the degree distribution with a total of N=30,000 nodes. Unfortunately, instead of being power-law distributed, the resulting distribution was exponential -- it was a straight line on a linear-log plot over several orders of magnitude. Clearly, I've done something wrong. While I would be happy to share the code I've written so far, before doing so, I wanted to make sure that I didn't have some sort of misunderstanding concerning how the algorithm was supposed to work in the first place. Here are the details concerning the algorithm as I've currently implemented it:

1. Create an initial completely connected graph with [latex] m_0 [/latex] nodes. I used [latex] m_0 = 10 [/latex] nodes because my understanding is that [latex] m_0 [/latex] should be small compared to N. By "completely connected", I mean a graph where every node is connected exactly once to every other node. So, for example, node 0 is connected to 9 other nodes: 1, 2, ..., 9, node 1 is also connected to 9 other nodes: 0, 2, 3, ..., 9, and so on.

2. Create a new node not yet connected to any other node -- call this new node n.

3. Select a node i in the original connected graph.

4. Draw a random number r from a uniform distribution on [0,1].

5. Set [latex] p = k_i/k_{tot} [/latex], where [latex] k_i [/latex] is the number of edges connected to node i and [latex] k_{tot} [/latex] is the sum of [latex] k_{j} [/latex] for all edges in the original connected graph. In other words, [latex] k_{tot} [/latex] is twice the number of edges in the entire graph.

6. If [latex] r < p [/latex], connect n to i. That is, add i to n's adjacency list and add n to i's adjacency list.

7. Repeat steps 2-6 until the graph has N = 30,000 nodes.

After completing steps 1-7, I have my program output the number of edges connected to every node. Then I use a simple script to construct a histogram. As I've said, the resulting distribution is exponential and not power-law as the distribution should be. Have I misunderstood the BA algorithm at some point?