diffusion_i.py

#coding=utf-8
from igraph import *
from sets import Set
import random
import copy
import math
def diffusion(g, beta=0.2, origin=0, timeLength=4040):
    print "beta:%f, origin:%d" % (beta,origin)
    lastNewSet = Set() # set of newly infected nodes in last timestep
    currentNewSet = Set() # set of newly infected nodes in current timestep
    currentNewSet.add(origin)
    result = {}
    result[0]=(0,0,0)
    for i in range(1,timeLength+1):
        lastNewSet = copy.deepcopy(currentNewSet)
        currentNewSet = Set()
        if len(lastNewSet)==0:
            break
        for n in lastNewSet:
            neighbors = [x.index for x in g.vs[n].neighbors()]
            for ne in neighbors:
                if not ne in result.keys():
                    r = random.random()
                    if r<beta:
                        currentNewSet.add(ne) # add to currentNewSet if infected
                        result[ne] = (ne,i,n) # node ne infected by n at time i
    print "i:",i
    return result

def f(node,sample,result):
    sample = list(sample)
    length = g.shortest_paths_dijkstra([node],sample) # matrix of length from node to sample node in sample
    s = 0
    #print "sample",sample
    #print "length",length[0]
    #print len(length[0])
    time = []
    for x in sample:
        if x in result.keys():
            time.append(result[x][1])
    #print "time",time
    #print len(time)
    for idx,val in enumerate(sample):
        # print "0 to observer %d: %d" % (val,length[0][idx])
        if val in result.keys():
            s += math.fabs(time[idx]-length[0][idx])
        else:
            print "%d not in result" % val
    print s
    return s

if __name__ == "__main__":
    g = Graph.Read_Pajek("facebook_combined.net")
    result = diffusion(g=g,beta=0.7)
    # sortedKey = sorted(result,key =lambda x:result[x][1]) # sort nodes in result by time 
    observers = Set([1,804,1506,1057,1195,1960,2368,2745,3027,3093,3869])
    sample = Set()
    for o in observers:
        neighbors = [x.index for x in g.vs[o].neighbors()]
        sample.add(o)
        sample.update(neighbors)
    for o in sample:
        if o in result.keys():
            pass
            # print result[o]
        else:
            print "not infected: %d" %o
    f(0,sample,result)
    test = [x.index for x in g.vs[0].neighbors()]
    for x in xrange(30):
        f(test[x],sample,result)