Barabasi-Albert Algorithm for Generating Scale-Free Graphs

[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 m₀ nodes. I used m₀=10 nodes because my understanding is that m₀ 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 [itex] p = k_i/k_{tot} [/itex], where [itex] p = k_i [/itex] is the number of edges connected to node i and [itex] k_{tot} [/itex] is the sum of [itex] k_j [/itex] for all edges in the original connected graph. In other words, [itex] k_{tot} [/itex] 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?

 

[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.

 

[dholbach]

ModestyKing -- Thanks for your reply!

In my code, k_tot is calculated by summing the degrees of every node. So, even if you were right, it wouldn't matter.

At any rate, the reason that k_tot is 2x the number of edges is because the edges are counted twice -- once at each node. Suppose we have a completely connected graph with five nodes. Each node is connected to four other nodes. So if we sum the edges over all of the nodes, we begin with node 0 and count its four connections -- to nodes 1, 2, and 3. Now we move to node 1 and count it's three connections -- to nodes 0, 2, and 3. But we've already counted the edge that connects node 0 to node 1, so the edge from node 0 to node 1 is counted twice. When we sum the number of connections over all of the nodes in the entire graph, we end up counting every edge twice, since we count any given edge at two nodes. That's why k_tot is twice the number of edges.