+ indep. WoS citations

Python and Networks -- Class notes -- 2016-03-03

### 1.  Generating a Scale-Free network and computing its degree distribution

#### 1.1  Python code (sf-ccdf.py)

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 =========

'''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
# same for node 1

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

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:
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

# connect the new node to each of the selected old nodes
for i in selOldNodeSet:
# the index of the new node is m+t

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


#### 1.2  How to use the code

python sf-ccdf.py 1000000 2 > sf-ccdf.txt