# A Barabasi-Albert Algorithm for Generating Scale-Free Graphs

1. Jul 29, 2016

### dholbach

I've been working on implementing the Barabasi-Albert model in C++. Barabasi-Albert networks are supposed to be scale-free -- that is, their degree distribution is supposed to be power-law distributed. In order to test whether my program was working correctly, I plotted the degree distribution from a network with a total of N=30,000 nodes. Unfortunately, I seem to have done something very wrong.

The resulting degree distribution from my program had a very nice, very clean exponential distribution and not a power-law distribution. On a linear-log plot, the degree distribution was a straight line for several orders of magnitude. While I'd be happy to share the relevant snippet of code at some point, I wanted to check to see if I've misunderstand BA algorithm at some important point.

1. Create an initial completely connected graph with m0 nodes. I used m0=10 nodes because my understanding is that m0 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 $p = k_i/k_{tot}$, where $p = k_i$ is the number of edges connected to node i and $k_{tot}$ is the sum of $k_j$ for all edges in the original connected graph. In other words, $k_{tot}$ is twice the number of edges in the entire graph.
6. If r < p, 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 an awk script to construct a histogram. The resulting distribution is exponential and not power-law; what gives? Have I misunderstood the BA algorithm at some point?

2. Aug 1, 2016

### ModestyKing

Maybe I'm tired and not thinking straight, but is k_tot really twice the number of edges in the entire graph? If m_0 = 10, then at the beginning any node n_i is connected to 9 edges. Since you have 10 nodes and each at the beginning is connected to 9 edges, k_tot is 9 * 10 = 90. Then k_tot is 10 times the number of edges in the whole graph in the beginning scenario, not twice the number. So your base case assumption is flawed, unless I'm messing up on my definitions. Did you implement the incorrect k_tot in an algorithm in this way (counting total no. of edges and doubling it) instead of manually?

Apologies if this is me misinterpreting something, my graph theory is really rusty.

3. Aug 1, 2016