Implementing Barabasi-Albert Method for Creating Scale-Free Networks

Question

I'm trying to implement a very simple preferential attachment algorithm for creating scale-free networks. These have degree distributions that follow a power-law, i.e. P(k) ~ k^-g, where g is the exponent. The algorithm below should produce degree distributions with the exponent equal 3 +/- 0.1, my implementation does not the exponents are closer to 2.5 +/- 0.1. I'm clearly not understanding something somewhere and continue to get it wrong. I'm sorry if this is in the wrong place, I couldn't decide whether it should be in stackoverflow or maths.stackexchange.com. ``` The Algorithm: Input: Number of Nodes N; Minimum degree d >= 1. Output: scale-free multigraph G = ({0,....,N-1}, E) M: array of length 2Nd for (v=0,...,n-1) for (i=0,...,d-1) M[2(vd+i)] = v; r = random number selected uniformly at random from {0,.....,2(vd+i)}; M[2(vd+i)+1] = M[r]; end end E = {}; for (i=0,...,nd-1) E[i] = {M[2i], M[2i+1]} end ``` My Implementation in C/C++: ``` void SF_LCD(std::vector< std::vector >…

Accepted Answer

Okay, so I couldn't figure out how to make this particular algorithm work correctly, instead I used another one.

```
The Algorithm:
Input: Number of Nodes N; 
       Initial number of nodes m0; 
       Offset Exponent a; 
       Minimum degree 1 <= d <= m0.
Output: scale-free multigraph G = ({0,....,N-1}, E).

1) Add m0 nodes to G.
2) Connect every node in G to every other node in G, i.e. create a complete graph.
3) Create a new node i.
4) Pick a node j uniformly at random from the graph G. Set P = (k(j)/k_tot)^a.
5) Pick a real number R uniformly at random between 0 and 1.
6) If P > R then add j to i's adjacency list.
7) Repeat steps 4 - 6 until i has m nodes in its adjacency list.
8) Add i to the adjacency list of each node in its adjacency list.
9) Add i to to the graph.
10) Repeat steps 3 - 9 until there are N nodes in the graph.
```

Where k(j) is the degree of node j in the graph G and k_tot is twice the number of edges (the total number of degrees) in the graph G.

By altering the parameter a one can control the exponent of the degree distribution. a = 1.22 gives me an exponent g (in P(k) ~ k^-g) of 3 +/- 0.1.

Implementing Barabasi-Albert Method for Creating Scale-Free Networks

Solution

Problem