+ indep. WoS citations

Python and Networks - Homework - 2016-03-08

Problem: Generate a Scale-Free network with \(N=10^6\) nodes and \(m=2\) links per new node. Initialize the network with a fully connected set of \(m\) nodes (an \(m\)-clique). Plot the degrees of two nodes as a function of time, \(t\): the node added at \(t=1\) to the network and the node added at \(t=100\). Note that \(t=n(t)-m\), where \(n(t)\) is the number of nodes in the network at time \(t\). The function sf can be a good start.

Solutions:

1.  FIJ

1.1  Python code (sf-growth.py)

import sys,random

# read parameters: 
# number of nodes (n), number of links per new node (m)
# time point when first node is added (t_null_1) and second node (t_null_2)
script, n, m, t_null_1, t_null_2 = sys.argv

# convert numbers to int
n = int(n); m = int(m); t_null_1 = int(t_null_1); t_null_2 = int(t_null_2)

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

def addLink(nodeIndxList, node2neiSet, node1, node2):
    '''Insert a link into the two book-keeping data structures'''

    # for both nodes:
    for node in (node1,node2):
        # add the two node indexes to the list of stub (link end point) indexes
        nodeIndxList.append(node)
        # if this node has no neighbors yet, then declare the set of its neighbors
        if not node2neiSet.has_key(node):
            node2neiSet[node] = set()

    # 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)

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

def sf2(n,m,tnSet):
    '''Generate a Scale-Free graph with parameters N and m
       Select some nodes by the times when they are added to the network, t_null
       For these nodes save the node degree at each time step, t
       Input: set of t_null values (birth time points) of the selected nodes
    '''

    # --- variables ---
    # a list containing each node as many times as its degree
    nodeIndxList = []    
    # for each node the set of its neighbors
    node2neiSet = {}
    # Returned data: t2tn2d[t]{tn}
    # at time t this is the degree of the node that was added to the network at time tn    
    t2tn2d = []

    # --- testing parameters and initializing ---

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

    # connect each pair among the first m nodes
    for node1 in range(m):
        node2 = node1
        while node2 <= m-1:
            addLink(nodeIndxList,node2neiSet,node1,node2)        
            node2 += 1

    # all requested tnull values have to be between 1 and n-m
    for tn in tnSet:
        if tn < 1 or tn > n-m:
            sys.exit("tn is not in [1, n-m]: %d" % tn)

    # --- iteratively: in each step add 1 new node and its m links ---
    for t in range(n-m):
        # select m old nodes to which the new node will be connected
        # select each old node with a probability proportional to its degree
        selOldNodeSet = set()
        # a set grows only when we add a different value, so
        # we will leave the while loop only after randomly selecting m different values
        while m > len(selOldNodeSet):
            # select one node index from the list of node indexes
            selOldNodeSet.add(nodeIndxList[random.randint(0, len(nodeIndxList)-1)])

        # connect the new node to each of the selected old nodes
        for i in selOldNodeSet:
            # the index of the new node is m+t
            addLink(nodeIndxList, node2neiSet, i, m+t)

        # declare the result dictionary for the current time point
        t2tn2d.append({})

        # for each of the requested nodes:
        for t_null in tnSet:
            # if the node has been already added to the network
            # NOTE: the array's 0 to (n-m-1) indexes correspond to times 1 to (n-m)
            if t+1 >= t_null:
                # then add its degree to this time point's dictionary                
                # the index of the node added at time t_null is m+(t_null-1)
                t2tn2d[t][t_null] = len(node2neiSet[m+t_null-1])

    # --- return value: node degrees ---
    return t2tn2d

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

def writeOutput(t2tn2d,tnSet):
    '''Write to stdout the node degrees of selected nodes as a function of time'''

    # print output header
    print "# Simulation time"

    # write column header for each t_null (each node's birth time point)
    numberOfTabs = 1
    for t_null in sorted(tnSet,key=int):
        print "#" + ( "\t" * numberOfTabs ) + "Degree of node added at t=%d" % t_null
        numberOfTabs += 1

    # separate header from data with an empty line
    print ""

    # write data
    for t in (range(len(t2tn2d))):
        # print simulation time point
        # NOTE: the array's 0 to (n-m-1) indexes correspond to times 1 to (n-m)
        sys.stdout.write("%d" % (t+1))
        # for each requested node:
        for tn in sorted(tnSet,key=int):
            # if the node has been added already
            if t+1 >= tn:
                # then print its degree
                sys.stdout.write("\t%d" % t2tn2d[t][tn])
            else:
                # otherwise print -
                sys.stdout.write("\t-")
        # print end of line    
        sys.stdout.write("\n")

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

# generate the network, save the degrees of the requested nodes as a function of time
t2tn2d = sf2(n,m,set([t_null_1,t_null_2]))

# write output header
writeOutput(t2tn2d,set([t_null_1,t_null_2]))

1.2  How to use the Python code

python sf-growth.py 1000000 2 10 100 > sf-growth-n1000000-m2.txt

1.3  Output data file (sf-growth-n1000000-m2.txt)

sf-growth-n1000000-m2.txt (15MB)

1.4  Gnuplot command file (sf-growth.gnu)

# settings
se term posts lands color enh dash "Helvetica" 22
se xlab "Elapsed time during the growth of an SF graph (N=10^6, m=2)" off -2,0
se ylab "Node degree" off 1,0
se grid
se o 'sf-growth.ps'
se key at 1500,2000 spacing 1.2
se log xy
se xtic ("1" 1, "10^2" 100, "10^4" 10000, "10^6" 1000000)
se ytic (1,10,100,1000)

# plot
p [.5:2e+6][1:3000] \
\
'sf-growth-n1000000-m2.txt' \
u 1:2 \
w l lt 1 lw 4 ti 'node added at t=1', \
\
'' \
u 1:3 \
w l lt 3 lw 4 ti 't=100'

1.5  Final image (sf-growth.ps)

2.  BGS

2.1  Python code

import sys,random

# read parameters: number of nodes (n), number of links per new node (m)
script, n, m = sys.argv

# convert numbers to int
n = int(n); m = int(m)

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

def addLink(nodeIndxList, node2neiSet, node1, node2):
    '''Insert a link into the two book-keeping data structures'''

    # for both nodes:
    for node in (node1,node2):
        # add the two node indexes to the list of stub (link end point) indexes
        nodeIndxList.append(node)
        #print ("newlink:",node)
        #print (node2)		
		#print sorted(nodeIndxList)		
		# if this node has no neighbors yet, then declare the set of its neighbors
        if not node2neiSet.has_key(node):
            node2neiSet[node] = set()

    # 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)

    #print nodeIndxList
# --------------------------------------

def sf(n,m,file,file2):    
    '''Generate a Scale-Free graph with parameters N and m'''

    # --- variables ---
    # a list containing each node as many times as its degree
    nodeIndxList = []    
    # for each node the set of its neighbors
    node2neiSet = {}

    # --- testing parameters and initializing ---
    # m >= 2
    if m < 2:
        sys.exit("The parameter m has to be at least 2")
    # connect each pair among the first m nodes
    for node1 in range(m):
        node2 = node1
        while node2 <= m-1:
            addLink(nodeIndxList,node2neiSet,node1,node2)        
            node2 += 1
    #print nodeIndxList
    #print node2neiSet
    # --- iteratively: in each step add 1 new node and its m links ---
    print("\n")	
    #print("Added links & nodes:\n")	
    x=0
    y=0
    for t in range(n-m):
        # select m old nodes to which the new node will be connected
        # select each old node with a probability proportional to its degree
        selOldNodeSet = set()
     #
		# a set grows only when we add a different value, so
        # we will leave the while loop only after randomly selecting m different values
        while m > len(selOldNodeSet):
            # select one node index from the list of node indexes
            selOldNodeSet.add(nodeIndxList[random.randint(0, len(nodeIndxList)-1)])
        #print "Old set:"
        #print selOldNodeSet
        # connect the new node to each of the selected old nodes
        for i in selOldNodeSet:
            # the index of the new node is m+t
            addLink(nodeIndxList, node2neiSet, i, m+t) 
        #print ("szomszedok:",node2neiSet)
        #print ("m+t:",m+t)		

        if(t>0 and len(node2neiSet[m+1]) > x):
           file.write("%d\t %lf\r\n" % (t,len(node2neiSet[m+1])))
           x=len(node2neiSet[m+1])
        if(t>99 and len(node2neiSet[m+100]) > y):   
           file2.write("%d\t %lf\r\n" % (t,len(node2neiSet[m+100])))
           y=len(node2neiSet[m+100])
		#print ("t:",t)
        #print ("hozzaadott csucs szomsz:",node2neiSet[m+t])
        #print ("hossz:",len(node2neiSet[m+t]))
        #print ("\n")
    # --- return value: the network ---
    #print nodeIndxList
    #print node2neiSet
    return node2neiSet

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

def from_node2neiSet_compute_nodeDeg2ccdf_writeToStdout(node2neiSet,numberOfNodes):
    '''Read network (node2neiSet), compute node degree CCDF, write to stdout'''

    # histogram[d]: the number of nodes that have d neighbors
    histogram = {}

    # the number of isolated nodes (i.e., nodes with zero node degree)
    histogram[0] = numberOfNodes - len(node2neiSet.keys())

    # node numbers with non-zero node degrees
    for node in node2neiSet.keys():
        # d: the degree of the current node        
        nodeDegree = len(node2neiSet[node])
        # if we see this node degree for the first time, then set its counter
        if not histogram.has_key(nodeDegree):
            histogram[nodeDegree] = 0
        # change the counter for this node degree
        histogram[nodeDegree] += 1

    # print output header
    print "# Node degree, 0 replaced with \"-\""
    print "#\tNode degree, 0 included"
    print "#\t\tCCDF"
    print ""

    # ccdf[d]: the probability for a node to have degree above d
    # compute the ccdf from the histogram
    # print output data
    ccdfNow = 1.0
    # loop through the keys of the histogram in ascending order
    for nodeDegree in sorted(histogram):
        # print nonzero node degree or "-"
        if 0 == nodeDegree:
            sys.stdout.write("-\t")
        else:
            sys.stdout.write("%d\t" % nodeDegree)
        # print node degree and CCDF only if CCDF is not 0 + numerical error
        if abs(ccdfNow) > numberOfNodes**(-2.0):
            print "%d\t%.5g" % (nodeDegree,ccdfNow)
        # step to next node degree
        ccdfNow -= histogram[nodeDegree]/(1.0*numberOfNodes)

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

# generate the network
file=open("BA1.dat", 'w')
file2=open("BA100.dat", 'w')
node2neiSet = sf(n,m,file,file2)

# compute node degree CCDF and write to stdout
#from_node2neiSet_compute_nodeDeg2ccdf_writeToStdout(node2neiSet,n)

2.2  Output (image)

3.  SZE

3.1  Python code

#skalafuggetlen halozat

# novekedes -- uj csucs a meglevo fokszamokkal (linearisan) aranyosan preferalja a mar meglevo eleket (fokszammal aranyos preferencialis kapcsolodas
# -> itt elofordulnak kiugroan nagy fokszamu csucsok


import random
from sys import argv

# t=0 -ban m0=m=2 db csucs
# kossuk ezeket ossze

# t-> (t+1)
# (t+1). pillanatban erkezik 1 uj csucs, aminek van m db ele. t ido utan: (t+m) csucs
# az m db el mindegyike a "regi" N=t+m db csucs kozul valaszt, barmelyiket a fokszamaval aranyos vszinuseggel (m db kulonbozo regi csucshoz kapcsolodik)


# halozat tarolasa
# minden csucshoz szomszedcsucsok halmazanak hozzarendelese


# preferencialis valasztas
# csucs indexet annyiszor irjuk be egy listaba, ahany ele van, ebbol valasztunk szamot

script, n,m=argv # n a csucsok max. szama, m csuccsal kezdunk t=n-m
n=int(n)
m=int(m)

def addlink(nodeIndxlist,node2neiSet,node1,node2):
    # add new link to index list
    for node in (node1,node2):
        nodeIndxlist.append(node)
        # add new link to the network
        # if a node has no neighbors yet, then declare its neighbor set
        if not node2neiSet.has_key(node):
            node2neiSet[node]=set()
    # node2 is a neighbor of node1
    node2neiSet[node1].add(node2)
    # same for node1
    node2neiSet[node2].add(node1)


def sf(n,m,nodedegree_1,nodedegree_100):
    # index of each node repeatedd as many times as the node's degree
    nodeIndxlist=[]

    # for each node: the set of its neighbors
    node2neiSet={}

    # initialize: add link to book-keeping 
    for i in range(m): # initialize with a fully connected m-clique
        for j in range(i): 
            addlink(nodeIndxlist,node2neiSet,i,j)

    for i in range (1,100,1): #igy megy 99-ig

        nodedegree_100[i]=0

    nodedegree_1[1]=m; nodedegree_100[100]=m;

    # time: from 1 to t=N-m -azt hiszem, eggyel kevesebbig megy, de ha +1-et irnek n-m-hez, akkor a nodedegree_-knel kifutna a valtozo a tombbol
    for t in range(1,n-m,1):

        # select m different "old" nodes
        selOldNodeSet=set()
        # select nodes one-by-one
        while len(selOldNodeSet)<m:

            # ha valami benne van a halmazban es megegyszer berakjuk, nem lesz valtozas 
            # => nem kell ellenorizni, h benne van-e

            selOldNodeSet.add(nodeIndxlist[random.randint(0,int(len(nodeIndxlist)-1))])

        #add link between new node and each old node
        for i in selOldNodeSet:
            addlink(nodeIndxlist,node2neiSet,i,m+t-1)


        # count the number of neighbors of the two given nodes
        increase_1=0; increase_100=0;

        for i in selOldNodeSet:
            if (i==m):
                increase_1=1
            if (i==m+99):
                increase_100=1
        if (t>1):
            nodedegree_1[t]=nodedegree_1[t-1]+increase_1
        if (t>100):
            nodedegree_100[t]=nodedegree_100[t-1]+increase_100


nodedegree_1=range(1,n-m+1,1); nodedegree_100=range(1,n-m+1,1)

sf(n,m,nodedegree_1,nodedegree_100)

for t in range(1,n-m,1):
    print "%d\t%d\t%d" % (t,nodedegree_1[t],nodedegree_100[t])

3.2  Output (image)

4.  DG

4.1  Python code

import sys
import random

script, n, m = sys.argv

# n is the number of nodes
n = int(n)
# m is the number of new edges per new node
m = int(m)

# For each node, its neighbors as a set.
# node_neighbors = { node1: { neighbor1, neighbor2, ... }, node2: {...} }
node_neighbors = {}

# A list containing each node as many times as its degree.
node_degree_distribution = []

if m < 1:
    print("m has to be at least 1!")
    exit()

# Connect n1 and n2 with an edge.
def connect_nodes(n1, n2):
    if not n1 in node_neighbors:
        node_neighbors[n1] = set()
    if not n2 in node_neighbors:
        node_neighbors[n2] = set()

    node_neighbors[n1].add(n2)
    node_neighbors[n2].add(n1)

    node_degree_distribution.append(n1)
    node_degree_distribution.append(n2)

# Initialize m nodes at the start.
# Initial network is a ring.
for i in range(m - 1):
    connect_nodes(i, i + 1)
connect_nodes(m - 1, 0)

# Two nodes we monitor.
node_neighbors[3] = set()
node_neighbors[102] = set()

print("#t degree_t_1_node degree_t_102_node")

# Generate network.
# Add n-m new nodes, one at every step, so the total number of nodes will be n.
for i in range(m + 1, n + 1):
    # i is the name of the new node.

    # Select m different nodes, with the probability of its degrees.
    new_connections = set()
    while len(new_connections) != m:
        new_connections.add(node_degree_distribution[random.randint(0, len(node_degree_distribution) - 1)])

    for k in new_connections:
        connect_nodes(i, k)

    # Print t=i-m-1, degree of the t=1 (i=3) node, degree of the t=100 (i=102th) node.
    print("%d %d %d" % (i - m - 1, len(node_neighbors[3]), len(node_neighbors[102])))

4.2  Output (image)

5.  KZS

5.1  Python code (sf.py)

#-*- coding: utf-8 -*-

import random as rnd
from sys import argv

#bevesszük a paramétereket:
script, N, m, node2monitor1, node2monitor2 = argv  #csúcsok száma, köt&#337;s m érték
N = int(N)
m = int(m)
node2monitor1 = int(node2monitor1)
node2monitor2 = int(node2monitor2)

#az új él (node1-node2) listákba beírására szolgáló függvény
def addLink(nodeIndexList, node2neiSet, node1, node2):
  for node in (node1, node2):
    nodeIndexList.append(node)

  #if a node has no neighbours, declare its neighbour-set:
  for node in (node1, node2):
    if not node2neiSet.has_key(node): 
      node2neiSet[node] = set()

  #add the nodes to each others neighbour-list:
  node2neiSet[node1].add(node2)
  node2neiSet[node2].add(node1)

def sf_graf_follow_node(N, m, node2monitor1, node2monitor2):
  #kell egy lista: minden csúcs indexe annyiszor, amennyi a fokszáma:
  nodeIndexList = []

  # a hálózatot tárolja:
  node2neiSet = {}

  # a két lekövetett fokszám: - egy mátrixban, minden sor egy adott id&#337;ben a két követett fokszám értéke
  degreesInTime = [[0]*2 for t in range (N-m)]


  #inicializálunk: m csúccsal
  # m >= 2 jó csak:
  if m < 2:
    sys.exit("The parameter m has to be at least 2")

  #0-tól m-1.ig minden csúcsot egy klikkben összekötök:
  for node1 in range(m):
    node2 = node1+1  #itt eltértem az el&#337;írt függvényt&#337;l!
    while node2 <= (m-1):
     addLink(nodeIndexList, node2neiSet, node1, node2)
     node2 += 1

  # elvégezzük a t. lépést: t=1-t&#337;l 
  for t in range(N-m):
    selOldNodeSet = set() #ezek azok a csúcsok, amikhez kötni fogjuk az új csúcsot! - SET-ben, hogy semmi se legyen meg 2x
    while len(selOldNodeSet) < m:
      selOldNodeSet.add(nodeIndexList[rnd.randint(0, len(nodeIndexList)-1)])

    #most be kell raknunk egy új élt minden kiv. régi csúcs és az új csúcsunk közé
    for i in selOldNodeSet:
      # az új él indexe m+t
      addLink(nodeIndexList, node2neiSet, i, m+t)

    #írjuk fel a monitorozott csúcsok aktuális fokszámát:
    if(node2neiSet.has_key(node2monitor1+m)):  #mi a node2monitor számban azt adjuk meg, milyen t-nél jön be -> a száma ez+m
      degreesInTime[t][0] = len(node2neiSet[node2monitor1+m])
    else:
      degreesInTime[t][0] = 0

    if(node2neiSet.has_key(node2monitor2+m)):
      degreesInTime[t][1] = len(node2neiSet[node2monitor2+m])
    else:
      degreesInTime[t][1] = 0

  return degreesInTime  #visszatérési értéke: a hálózat

nodeDegrees = sf_graf_follow_node(N, m, node2monitor1, node2monitor2)

#print the results:
print "#Time Node1_degree Node2_degree"
for t in range (N-m):
  print (t+1), nodeDegrees[t][0], nodeDegrees[t][1]

5.2  How to use the python code

python2 sf.py 1000000 2 0 99 > hf_4_output.txt

5.3  Output file (hf_4_output.txt)

5.4  Gnuplot command file

set term png enhance
set title "Degrees of two nodes in a growing SF-network \n N={10^6}"
set output "hf_4_output_loglogscale.png"                                                             
set xlabel "Time (t)"
set ylabel "Node degree"
set key left top
set key at 2, 700
set key font ",12"
set key spacing 6
set key box lc 0
set xtics (10, 100, 1000, 10000, 100000)
set logscale xy
plot 'hf_4_output.txt' u 1:2 w p lc rgb "#CC1459" pt 4 ps 0.6 title "Node added at t=1", \
     'hf_4_output.txt' u 1:3 w p lc rgb "#FFE800" pt 4 ps 0.6 title "Node added at t=100"
set output

5.5  Output (image)

6.  BB

6.1  Python code

import random
import matplotlib.pyplot as plt
from sys import argv

# function for adding new links to the network
def addLink(nodeIndexList, node2neiSet, node1, node2) :

    for node in (node1, node2) :
        # add new link to index list
        nodeIndexList.append(node)

        # if a node has no neigbours yet, then declare its neigbours
        if not node2neiSet.has_key(node) :
            node2neiSet[node] = set()


    node2neiSet[node1].add(node2)
    node2neiSet[node2].add(node1)

# generate scale-free network
def sf(n, m) :
    # index of each node repeated as many times as the node's degree
    nodeIndexList = []

    # for each node: the set of its neigbours
    node2neiSet = {}
    # initialize: add link to the book-keeping
    for i in range(m - 1) :
        addLink(nodeIndexList, node2neiSet, i + 1, i)

    # index of the nodes, for which we want to check how is their degree evolving over time
    idx1 = 1 + (m-1);         # index of node added at t = 1
    idx2 = 100 + (m-1);       # index of node added at t = 100

    # the degree of the node added at t = 1, and t = 100 as a function of t
    n1Degree_t = [0]*(n-m+1)
    n2Degree_t = [0]*(n-m+1)

    # each node will exactly m degree, when it is added to the network.
    n1Degree_t[idx1 - 1] = m
    n2Degree_t[idx2 - 1] = m
    # in each step add a new node, and link them to m different nodes
    for t in range(n - m) :
        # select m different "old" nodes
        selOldNodeSet = set()

        # select old nodes one-by-one
        while  len(selOldNodeSet) < m :
            selOldNodeSet.add(nodeIndexList[random.randint(0, len(nodeIndexList) - 1)])

        # add link between new nodes and each  old node
        for i in selOldNodeSet :
            addLink(nodeIndexList, node2neiSet, i, m + t)

            # update the degrees of the targed nodes over time
            # the [t+1] is needed, because at this point we already have t+1 new nodes added to the network
            if t+m > idx1 and i == idx1:
                n1Degree_t[t+1] = n1Degree_t[t] + 1

            if t+m > idx2 and i == idx2:
                n2Degree_t[t+1] = n2Degree_t[t] + 1

        # if we have did not increased the degree of our target nodes, we copy the values from the previous step
        if n1Degree_t[t+1] == 0 :
            n1Degree_t[t+1] = n1Degree_t[t]

        if n2Degree_t[t+1] == 0 :
            n2Degree_t[t+1] = n2Degree_t[t]


    time = range(n - m + 1)

    plt.xlabel("time")
    plt.ylabel("degree")
    plt.title("Degree of the nodes added at t = 1 and t = 100")
    plt.xscale('log')
    plt.yscale('log')
    plt.plot(time, n1Degree_t, '.', label = "t = 1")
    plt.plot(time, n2Degree_t, '.', label = "t = 100")
    plt.show()

# input parameters: n - number of nodes, m - number of new links
script, n, m = argv # n - max number of nodes; m - number of new edges per new node
n = int(n)
m = int(m)
sf(n,m)

6.2  Output (image)

7.  JM

7.1  Python code

import sys,random

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

def addLink(nodeIndxList, node2neiSet, node1, node2):
    '''Insert a link into the two book-keeping data structures'''

    # for both nodes:
    for node in (node1,node2):
        # add the two node indexes to the list of stub (link end point) indexes
        nodeIndxList.append(node)
        # if this node has no neighbors yet, then declare the set of its neighbors
        if not node2neiSet.has_key(node):
            node2neiSet[node] = set()

    # 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)

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

def sf(n,m):    
    '''Generate a Scale-Free graph with parameters N and m'''

    # --- variables ---
    # a list containing each node as many times as its degree
    nodeIndxList = []    
    # for each node the set of its neighbors
    node2neiSet = {}


    # --- testing parameters and initializing ---
    # m >= 2
    if m < 2:
        sys.exit("The parameter m has to be at least 2")
    # connect each pair among the first m nodes
    for node1 in range(m):
        node2 = node1
        while node2 <= m-1:
            addLink(nodeIndxList,node2neiSet,node1,node2)        
            node2 += 1

    # --- iteratively: in each step add 1 new node and its m links ---
    for t in range(n-m):
        # select m old nodes to which the new node will be connected
        # select each old node with a probability proportional to its degree
        selOldNodeSet = set()
        # a set grows only when we add a different value, so
        # we will leave the while loop only after randomly selecting m different values
        while m > len(selOldNodeSet):
            # select one node index from the list of node indexes
            selOldNodeSet.add(nodeIndxList[random.randint(0, len(nodeIndxList)-1)])

       # printing the current node degree values vs time
        if (t+1 > 100):
            print t+1, len(node2neiSet[0]), len(node2neiSet[98])  
        else:
            print t+1, len(node2neiSet[0])  
        # connect the new node to each of the selected old nodes
        for i in selOldNodeSet:
            # the index of the new node is m+t
            addLink(nodeIndxList, node2neiSet, i, m+t)

    # --- return value: the network ---
    return node2neiSet

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

# generate the network

n = 100000
m = 2

node2neiSet = sf(n,m)

7.2  Output data file

7.3  Output image

8.  PD

8.1  Python code

import sys,random
# read parameters: number of nodes (n), number of links per new node (m)

script, n, m = sys.argv
# convert numbers to int
n = int(n); m = int(m)

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

def addLink(nodeIndxList, node2neiSet, node1, node2):

    #'''Insert a link into the two book-keeping data structures'''
    # for both nodes:
    for node in (node1,node2):
        # add the two node indexes to the list of stub (link end point) indexes
        nodeIndxList.append(node)
        # if this node has no neighbors yet, then declare the set of its neighbors
        if not node2neiSet.has_key(node):
            node2neiSet[node] = set()
    # 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)
# --------------------------------------
def sf(n,m):   
    #'''Generate a Scale-Free graph with parameters N and m'''
    # --- variables ---
    # a list containing each node as many times as its degree
    nodeIndxList = []   
    # for each node the set of its neighbors
    node2neiSet = {}
    # --- testing parameters and initializing ---
    # m >= 2
    if m < 2:
        sys.exit("The parameter m has to be at least 2")
    # connect each pair among the first m nodes
    for node1 in range(m):
        node2 = node1
        while node2 <= m-1:
            addLink(nodeIndxList,node2neiSet,node1,node2)       
            node2 += 1
    # --- iteratively: in each step add 1 new node and its m links ---
    # definialok ket uj valtozot amik a t=0-ban es a t=100ban vett csucsok lesznek
    t0=0;	t100=0
    # kelleni fog ket uj fajl, hogy eltaroljam a kello ertekeket
    f=open("d_papp4_1.dat",'w')
    g=open("d_papp4_2.dat",'w')	
    for t in range(n-m):
        # select m old nodes to which the new node will be connected
        # select each old node with a probability proportional to its degree
        selOldNodeSet = set()
        # a set grows only when we add a different value, so
        # we will leave the while loop only after randomly selecting m different values
        while m > len(selOldNodeSet):
            # select one node index from the list of node indexes
            selOldNodeSet.add(nodeIndxList[random.randint(0, len(nodeIndxList)-1)])
        # connect the new node to each of the selected old nodes
        for i in selOldNodeSet:
            # the index of the new node is m+t
            addLink(nodeIndxList, node2neiSet, i, m+t)
	if(t>0 and len(node2neiSet[m+1])>t0 ):
	    f.write("%d\t %lf\r\n" % (t,len(node2neiSet[m+1])))	
	    t0=len(node2neiSet[m+1])	
	if(t>99 and len(node2neiSet[m+100])>t100):
	    g.write("%d\t %lf\r\n" % (t,len(node2neiSet[m+100])))
            t100=len(node2neiSet[0+100])
    # --- return value: the network ---
    return node2neiSet
# --------------------------------------
def from_node2neiSet_compute_nodeDeg2ccdf_writeToStdout(node2neiSet,numberOfNodes):
    '''Read network (node2neiSet), compute node degree CCDF, write to stdout'''
    # histogram[d]: the number of nodes that have d neighbors
    histogram = {}
    # the number of isolated nodes (i.e., nodes with zero node degree)
    histogram[0] = numberOfNodes - len(node2neiSet.keys())
    # node numbers with non-zero node degrees
    for node in node2neiSet.keys():
        # d: the degree of the current node       
        nodeDegree = len(node2neiSet[node])
        # if we see this node degree for the first time, then set its counter
        if not histogram.has_key(nodeDegree):
            histogram[nodeDegree] = 0
        # change the counter for this node degree
        histogram[nodeDegree] += 1
    # print output header
    print "# Node degree, 0 replaced with \"-\""
    print "#\tNode degree, 0 included"
    print "#\t\tCCDF"
    print ""
    # ccdf[d]: the probability for a node to have degree above d
    # compute the ccdf from the histogram
    # print output data
    ccdfNow = 1.0
    # loop through the keys of the histogram in ascending order
    for nodeDegree in sorted(histogram):
        # print nonzero node degree or "-"
        if 0 == nodeDegree:
            sys.stdout.write("-\t")
        else:
            sys.stdout.write("%d\t" % nodeDegree)
        # print node degree and CCDF only if CCDF is not 0 + numerical error
        if abs(ccdfNow) > numberOfNodes**(-2.0):
            print "%d\t%.5g" % (nodeDegree,ccdfNow)
        # step to next node degree
        ccdfNow -= histogram[nodeDegree]/(1.0*numberOfNodes)
# ========= main =========
# generate the network
node2neiSet = sf(n,m)
# compute node degree CCDF and write to stdout
from_node2neiSet_compute_nodeDeg2ccdf_writeToStdout(node2neiSet,n)

8.2  Output image

9.  SZT

9.1  Python code (hw4.py)

# Python programming and networks - Homework 4
# Szorenyi Tamas
# Generate a Scale-Free network with N=10^6 nodes and m=2 links per new node.
# Initialize the network with a fully connected set of m nodes (an m-clique).
# Plot the degrees of two nodes as a function of time, t: the node added at t=1 to the network and the node added at t=100.
# Note that t=n(t)-m, where n(t) is the number of nodes in the network at time t. The function sf can be a good start.

import sys,random

# read parameters: number of nodes (n), number of links per new node (m)
script, n, m = sys.argv

# convert numbers to int
n = int(n); m = int(m)

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

def addLink(nodeIndxList, node2neiSet, node1, node2):
    '''Insert a link into the two book-keeping data structures'''

    # for both nodes:
    for node in (node1,node2):
        # add the two node indexes to the list of stub (link end point) indexes
        nodeIndxList.append(node)
        # if this node has no neighbors yet, then declare the set of its neighbors
        if not node2neiSet.has_key(node):
            node2neiSet[node] = set()

    # 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)

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

def sf(n,m):    
    '''Generate a Scale-Free graph with parameters N and m'''

    # --- variables ---
    # a list containing each node as many times as its degree
    nodeIndxList = []    
    # for each node the set of its neighbors
    node2neiSet = {}

    # --- testing parameters and initializing ---
    # m >= 2
    if m < 2:
        sys.exit("The parameter m has to be at least 2")
    # connect each pair among the first m nodes
    for node1 in range(m):
        node2 = node1
        while node2 <= m-1:
            addLink(nodeIndxList,node2neiSet,node1,node2)        
            node2 += 1

    # --- iteratively: in each step add 1 new node and its m links ---
    for t in range(n-m):
        # select m old nodes to which the new node will be connected
        # select each old node with a probability proportional to its degree
		selOldNodeSet = set()
        # a set grows only when we add a different value, so
        # we will leave the while loop only after randomly selecting m different values
		while m > len(selOldNodeSet):
            # select one node index from the list of node indexes
			selOldNodeSet.add(nodeIndxList[random.randint(0, len(nodeIndxList)-1)])

		# Now print current time and node degree
		if t < 100:
			print "%d\t%d" % (t+1, len(node2neiSet[0]))
		else:
			print "%d\t%d\t%d" % (t+1, len(node2neiSet[0]), len(node2neiSet[98]))

		# connect the new node to each of the selected old nodes
		for i in selOldNodeSet:
            # the index of the new node is m+t
			addLink(nodeIndxList, node2neiSet, i, m+t)

    # --- return value: the network ---
    return node2neiSet

print "# Time"
print "#	Degree of node 1 (added at t=1)"
print "#		Degree of node 2 (added at t=100)"
# generate the network
node2neiSet = sf(n,m)

9.2  Shell script

#!/bin/bash

python hw4.py 1000000 2 > hw4data.txt

gnuplot -persist << EOPLOT

set terminal png
set xlabel "Time"
set ylabel "Node degree"
set logscale xy
set xrange [0.5:1500000]
set yrange [0.5:15000]
set grid
set key box
set out "hw4plot.png"
plot "hw4data.txt" u 1:2 w l lw 2 t "Node 1 (added at t=1)", "hw4data.txt" u 1:3 w l lw 2 t "Node 2 (added at t=100)"

EOPLOT

9.3  Output image