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

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

        # 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

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

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)

1.2  How to use the code

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

1.3  Output (example)

sf-ccdf.txt (5kB)