+ indep. WoS citations

Python and Networks // Homework 2017-03-21 // SF model largest node degree

Problem

Generate a Scale-Free network with the model of Barabasi, Albert and Jeong. At \(t_0=0\) initialize the network with a fully connected set of \(m_0=2\) nodes (i.e., a single link) and set \(m=2\). Run the algorithm for \(t_{max}=10^6\) steps. Plot the largest node degree, \(d_{max}\), as a function of the number of steps, \(t\).

Solution (example)

1.  Python code (sf.py)

import sys,random
import numpy as np
import matplotlib.pyplot as plt

# read parameters: number of time steps (tmax), number of links per new node (m)
# save the largest node degree always when the time reaches tr * previous time
_, tmax, m, tr, outFileTxt, outFileImg = sys.argv

# convert numbers to int and float
tmax = int(tmax); m = int(m); tr = float(tr)

# ========= function definitions =========

def addLink(nodeIndxList, node2neiSet, d, node1, node2):
    '''Connect the two nodes <node1> and <node2>:
       change the book-keeping data structures'''

    # --- check if both nodes already have neighbors ---
    # for both nodes:
    for node in (node1,node2):
        # IF this node has no neighbors yet,
        if not node2neiSet.has_key(node):
            # THEN declare the set of its neighbors
            node2neiSet[node] = set()

    # --- connect the two nodes ---
    # add the 2nd node to the set of neighbors of the 1st node
    node2neiSet[node1].add(node2)
    # same for node 1
    node2neiSet[node2].add(node1)
    # for both nodes:
    for node in (node1,node2):
        # append node index to the list of node indexes counting node degrees
        nodeIndxList.append(node)
        # the node has one new neighbor, increment its degree
        d[node] += 1

# --------------------------------------

def sf(tmax,m,t2dmax,tr):
    '''Generate a Scale-Free graph, time steps: t, links per new node: m,
       initialize with a fully connected subgraph of m nodes'''

    # --- testing parameters ---
    # m >= 2
    if m < 2:
        sys.exit("The parameter m has to be at least 2")

    # --- variables and initialization ---
    # node2neiSet{node} is the set of the neighbors of <node>
    node2neiSet = {}
    # list contains any node as many times as its degree (number of neighbors)
    nodeIndxList = []    
    # d[node] is degree of <node>, at t=0 all m initial nodes have d = 0
    d = [0] * m
    # fully connect the first m nodes
    for nodeA in range(m):
        for nodeB in np.arange(nodeA+1,m):
            addLink(nodeIndxList,node2neiSet,d,nodeA,nodeB)
    # set the largest node degree at t=0: it is m-1
    t2dmax[0] = m-1
    # time when dmax was saved last
    t_last = 0

    # --- iteratively: in each step add 1 new node and its m links ---
    for t in np.arange(1,tmax+1):
        # declare the degree of the new node
        d.append(0)
        # - select m old nodes to which the new node will be connected
        # - select each old node with a probability proportional
        #   to its degree before the current/new node came
        selOldNodeSet = set()
        # a set grows only when we add a different value, so
        # we will leave the while loop only after
        # we have managed to randomly select m different values
        while m > len(selOldNodeSet):
            # select one node index from the list that contains each
            # node index as many times as the degree of that node
            selOldNodeSet.add(nodeIndxList[random.randint(0, len(nodeIndxList)-1)])
        # connect the new node to each of the selected old nodes
        for indxOfOldNode in selOldNodeSet:
            # the index of the new node is m+t-1
            addLink(nodeIndxList, node2neiSet, d, indxOfOldNode, m+t-1)
        # IF the current time is higher than tr (t ratio) times the previous time
        # OR we are at the last time step
        if 1.0 * t >= tr * t_last or 0 == t-tmax:
            # THEN save the current dmax
            t2dmax[t] = np.amax(d)
            # AND set the time of saving the to current time
            t_last = t

# --------------------------------------

def printPlotDmax(t2dmax,m,tr,tmax,outFileTxt,outFileImg):

    # --- output txt file ---
    # open text output file
    with open(outFileTxt,"w") as f:
        # print file header
        f.write("# Largest node degree in a SF network (Physica A 1999, 272:173)\n")
        f.write("# m = m_0 = %d, printing d_max at steps that have a ratio of %g\n" % (m,tr**2.0) )
        f.write("#\n")
        f.write("# t (number of time steps)\n")
        f.write("#\td_max (largest node degree)\n")
        f.write("\n") # blank line to separate header from data
        # print data
        for t in sorted(t2dmax):
            f.write("%d\t%g\n" % (t,t2dmax[t]))

    # --- output figure ---
    # initialize the output figure
    fig, ax = plt.subplots()
    # set log-log axes, clip non-positive values
    ax.set_xscale("log", nonposx='clip')
    ax.set_yscale("log", nonposy='clip')
    # set axis limits
    ax.set_xlim(left=1.0/tr**2.0,right=tr**2.0*tmax)
    ax.set_ylim(bottom=t2dmax[0]/tr**2.0,top=tr**2.0*t2dmax[np.max(t2dmax.keys())])
    # set axis labels and plot title
    ax.set_xlabel('t: number of time steps')
    ax.set_ylabel('d_max: largest node degree')
    plt.title("Largest node degree of an SF network, m=m_0=%d" % m)
    # plot data points: the value of the dict (y) vs its keys (x)
    x = sorted( t2dmax.keys() )
    y = [ t2dmax[ t ] for t in x ]
    plt.loglog(x,y,marker='o',mec='r',mfc='w',mew=2,linestyle='None')
    # export figure and close the figure
    fig.savefig(outFileImg)
    plt.close(fig)

# ========= main =========

# generate the network
# t2dmax[t] is the largest node degree after tmax time steps,
# save its value every time that the time grows by a ratio of tr
t2dmax = {}; sf(tmax,m,t2dmax,tr)

# print and plot the largest node degree
printPlotDmax(t2dmax,m,tr,tmax,outFileTxt,outFileImg)

2.  How to use the Python code

python3 sf.py 1000000 2 1.2 sf.txt sf.png

3.  Output image (sf.png)

4.  Text output file (sf.txt)

# Largest node degree in a SF network (Physica A 1999, 272:173)
# m = m_0 = 2, printing d_max at steps that have a ratio of 1.44
#
# t (number of time steps)
#       d_max (largest node degree)

0       1
1       2
2       3
3       4
4       5
5       6
6       7
8       8
10      10
12      12
15      13
18      14
22      15
27      17
33      20
40      21
48      22
58      23
70      26
84      27
101     31
122     33
147     36
177     39
213     41
256     42
308     47
370     54
444     58
533     64
640     68
768     72
922     75
1107    82
1329    86
1595    94
1914    110
2297    123
2757    133
3309    145
3971    161
4766    176
5720    194
6864    204
8237    228
9885    245
11862   261
14235   281
17082   308
20499   344
24599   371
29519   409
35423   460
42508   501
51010   553
61212   606
73455   657
88146   732
105776  798
126932  877
152319  953
182783  1050
219340  1140
263208  1251
315850  1381
379020  1534
454824  1695
545789  1849
654947  2001
785937  2194
943125  2414
1000000 2488