algorithmmatlabcomplex-networks

Preferential Attachment, Complex Networks in Matlab

Hej everyone!

I am right now working on a preferential attachment model in MATLAB and I have some troubles to understand the following:

Assuming I have 4 nodes in the beginning, connected like this: 

time = 0  
1 <-----> 2  
3 <-----> 4

In the next time step I add a single node and 4 connections, then another single node and 4 connections.
The formula for my linking probability to node i is: 

P_link(i) = degree(i) / sum of all degrees at time-1

This results in the probabilities of 1/4 for each of the nodes i = 1 to 4 in the first step and then, having node 5 connected to 1, 2, 3 and 4, I will have a "sum of degrees" = 12, when adding node 6 in the following time step.
That then means the linking probabilities are: 1/6, 1/6, 1/6, 1/6 and 1/3.

How can I set this up in MATLAB? My problem is, I normally write these things on paper to get a better understanding, and if there is a randomisation I just "simulate" it on paper to compare it with a simple MATLAB program.

What I would now do is: I take a random number, let's say 0.3045.
To add this to a node it would have to be in the range of 

node1: [0.0000, 1/6],  
node2: [1/6, 1/3],  
node3: [1/3, 1/2],  
node4: [1/2, 2/3],  
node5: [2/3, 1.0000].  
---> CONNECT to node2

So for the first step I have an idea of how to do it, but now I have two different problems, which are, I think, closely related:

  1. How am I able to implement this in MATLAB, is the range approach a good idea?
  2. How do the probablities change after adding the first connection for the rest, assuming it can only be connected once to each node? (this might be a more mathematical question I have to admit ...)

I am very sorry, this question looks so messy, but I hope someone can give me some hints about the implementation of this.
Thanks in advance!

Solution

  • I would do the following...

    Having your Adjacency matrix

    >> A = [0 1 0 0; 1 0 0 0; 0 0 0 1; 0 0 1 0]

    and Degrees matrix

    >> D = sum(A)

    In every iteration, the degree of any vertex i is D(i) and total number of degrees is 

    >> d = sum(D)

    Note, that you want to obtain d prior to the first iteration, and then again at the very end of iteration loop, so that it remains with value of time-1, in which case you might want to normalize P by doing

    >> P = P ./ max(P)

    Probabilities of picking any vertex (ie. your range approach simplified) are then calculated

    >> P = cumsum(D ./ d)
ans = [0.2500, 0.5000, 0.7500, 1.0000]

    And with random scalar number r from range <0,1>, you choose index i of randomly selected vertex by

    >> i = find([-1 P]<r, 1, 'last')

    And to push the new vertex with index j to A, connecting it to old vertex i, you simply

    >> A(i, j) = 1
>> A(j, i) = 1

    Now you simply enclose everything in loop and voilà you problem solved ;]