After June 2017 please see http://linkedin.com/in/illesfarkas. Thank you.
|
|
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) Contents (hide) 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 codepython3 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 |
