In [1]:
import numpy as np
import random as rnd
import matplotlib.pyplot as plt

%matplotlib inline
In [11]:
#this function generates the BA scale free graph and returns how the max degree increased trough time
#parametrs: t=time, m0 initial node number (FC), m number of links for every node 
#returns: max_degrees
def get_SF_maxdegree(t, m=2, m0=2):
    #degree dict
    degrees = {}
    #max degree node in t
    mdn = 0
    #max degree in t
    md  = m0-1
    # contains the nodes as many times as it's degree
    nodeList = []
    # max degrees
    max_degrees = []
    #initialize the FC graph at t=0
    for i in range(m0):
        # connecting the node with all of the other nodes
        #edges[i] = set([j for j in range(m0) if i!=j])
        # adding the i node to nodeList as many times as it's degree
        nodeList.extend([i]*m0)
        degrees[i] = m0
    #iterating trough time, time step also used as node index
    #but I already have 0,..., m0 nodes, so I shift the loop
    for i in range(m0,t+m0):
        #selected nodes: this nodes will be connected to the new node
        selected_nodes = []
        #we try to select node until we have selected m node
        while len(selected_nodes)!=m:
            # selecting a node, nodeList contains a node as many times as it's degree. 
            # So the probability of selecting node is propto it's degree.
            sn = nodeList[rnd.randint(0, len(nodeList)-1)]
            # if we already selected this node, we don't select it again, 
            # because we can't connect multiple times the same two node
            if sn not in selected_nodes:
                # adding the selected node to the selected_nodes list
                selected_nodes.append(sn)
                # if sn is the max degree node, then de max degree is increased now with 1
                if sn==mdn:
                    md += 1
                degrees[sn] += 1
                # if the new node degree is bigger then md then we have a new max degree node
                if degrees[sn]>md:
                    md  = degrees[sn]
                    mdn = sn
        # adding the selected nodes to nodeList
        nodeList.extend(selected_nodes)
        # adding the new node to the nodeList as many times as it's degree, which is m
        nodeList.extend([i]*m)
        # adding the new node to degrees dict
        degrees[i] = m
        # if the new node degree's > max degree: we have a new max degree node
        if m>md:
            md  = m
            mdn = i
        max_degrees.append(md)
    return max_degrees
In [16]:
# getting the degree increase for t=10^6
degrees = get_SF_maxdegree(1000000)
In [17]:
# creating the time list
time = [i for i in range(len(degrees))]
In [31]:
#plot
plt.figure(0, (12,7))
plt.xlim([-max(time)*0.02, max(time)*1.02])
plt.ylim([-max(degrees)*0.02, max(degrees)*1.02])
plt.xlabel("Time", fontsize=18)
plt.ylabel("Max degree", fontsize=18)
plt.plot(time, degrees)
Out[31]:
[<matplotlib.lines.Line2D at 0x1f71c05e4a8>]