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