100 trials

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 13 18:38:04 2016

@author: Dyuti
"""
# independent cascade model

from __future__ import division
import networkx as nx
from collections import deque
import random
import operator
from copy import deepcopy
import numpy as np

import sys

WHITE = 0
GRAY = 1
BLACK = 2

#======================================================================
def read_graph(filename):
    G = nx.DiGraph()
    with open(filename, 'r') as f:
        for line in f.readlines():
            u, v = map(int, line.split())
            G.add_edge(u, v)
            G.add_edge(v, u)
    return G


#======================================================================


def createw(G):

    "this function creates the edge weight of all edges in the edgelist"
    rank = list()
    weight = list()
    ex= nx.pagerank(G)
    for edge in G.edges_iter():
        u, v = edge
        wt = ex[u] * ex[v] / sum(ex[i] for i in G.neighbors_iter(v))
        rank.append((u, v, wt))
    sortdic = sorted(rank, reverse=True, key=operator.itemgetter(2))
    #rank_diffuse = deepcopy(sortdic)
   #normalization
    m = len(G.edges())
    for i, thing in enumerate(sortdic):
        u, v, w = thing
        min = sortdic[len(sortdic)-1][2]
        max = sortdic[0][2]
        wt = ex[u] * ex[v] / sum(ex[i] for i in G.neighbors_iter(v))
        wt1 = (sortdic[i][2]-min)/(max-min)
        weight.append(wt1)
        G[u][v]['weight'] = wt1

    return weight

#======================================================================

def prRank(G):
    ex = nx.pagerank_numpy(G)
    listpr= sorted(ex.items(), reverse = True , key=operator.itemgetter(1))
    #first 10 values
    listpr = [x[0] for x in listpr[:10]]
    #first 100 values
    #listpr = [x[0] for x in listpr[:100]]
    #first 10% nodes
    #n=int(len(G.nodes())*0.1)
    #listpr = [x[0] for x in listpr[:n]]
    return listpr

#======================================================================

def degreeRank(G):
    ex=nx.degree_centrality(G)
    listpr= sorted(ex.items(), reverse = True , key=operator.itemgetter(1))
    #first 10 values
    #listpr = [x[0] for x in listpr[:10]]
    #first 100 values
    #listpr = [x[0] for x in listpr[:100]]
    #first 10% nodes
    n=int(len(G.nodes())*0.1)
    listpr = [x[0] for x in listpr[:n]]
    return listpr

#======================================================================

def independent_cascade(G, seeds, weight):
    '''
    runs the independent cascade model on the graph G where edge weights represent the respective
    propagation probabilities

    seeds is a set of seed nodes
    returns the fraction of spread
    '''
    color = {}
    for node in G.nodes_iter():
        if node in seeds:
            color[node] = GRAY
        else:
            color[node] = WHITE

    Q = deque(seeds)

    spread_count = len(seeds)
    while len(Q) != 0:
        u = Q.popleft()
        for v in G.neighbors_iter(u):
            if color[v] == WHITE:
                # BECAUSE THE DIFFUSION HAS TO BE FAIr
                r = random.choice(weight)
                if r < G[u][v]['weight']:
                    Q.append(v)
                    color[v] = GRAY
                    spread_count += 1
        color[u] = BLACK

        #print spread_count
    return spread_count / G.order()


#======================================================================

def main():
    x = []
    G = read_graph('eron.txt')

    for u, v in karate.edges_iter():
        G.add_edge(u, v)
        G.add_edge(v, u)


    mean = createw(G)

    for i in xrange(100):
        listcSum = prRank(G)
        x.append(independent_cascade(G, listcSum,mean))

    print x
    print 'mean',np.mean(x)
    print 'std',np.std(x)



if __name__== '__main__':
    main()