Fastest possible contagion algorithm with iGraph

Question

I'm trying to write a contagion algorithm that:

1. creates an igraph graph
2. lits up four random nodes with, say, a fire (state = True)
3. spreads the fire to another node if a least 10% of its neighbors are on fire. The node which spread the fire it exhausted (state = False)
4. stop when no node is on fire.

Here's my code so far:

from igraph import *
from random import *
from time import *

def countSimilarNeigh(g,v):
    c = 0
    neigh = g.neighbors(v[0])
    for v2 in neigh:
        if g.vs(v2)['state'] != v['state']:
            c += 1
    return float(c)/len(neigh)

def contagion(g):
    contagious = True
    while contagious:
        for v in g.vs():
            contagious = False
            if v['contagious'] == True:
                for n2 in g.neighbors(v):
                    if countSimilarNeigh(g,g.vs(n2)) > 0.1 and g.vs(n2)['state'][0] == False:
                        g.vs(n2)['state'] = True
                        g.vs(n2)['contagious'] = True
                        contagious = True
            v['contagious'] = False

def init_graph(n = 60, p = .1):
    g = Graph.Erdos_Renyi(n,p)                
    while g.is_connected == False:
        g = Graph.Erdos_Renyi(n,p)
    g.simplify(multiple=True, loops=True)
    return g


def score(g,repl = 200):
    for c in range(repl):
        cc = 0
        for i in g.vs():
            i['contagious'] = False
            i['state'] = False
            if random() < .1 and cc < 4:
                i['state'] = True
                i['contagious'] = True
                cc += 1
        contagion(g)

t0 = time()    
score(init_graph())
print time()-t0

It runs pretty slow on my computer unfortunately, and I need to compute a lot of replicates. Is there a way to optimize this code, or maybe use a different method to perform a contagion in a much more efficient way?

I based this algorithm on http://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/

Edit: a run with cprofiler provides a little more informations. countSimilarNeigh() uses up the most ressources, by far:

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  200    0.147    0.001    2.391    0.012 Untitled:14(contagion)
    1    0.000    0.000    0.000    0.000 Untitled:28(init_graph)
    1    0.005    0.005    2.398    2.398 Untitled:36(score)
61392    0.601    0.000    1.925    0.000 Untitled:5(countSimilarNeigh)

Answer 1

I think you are duplicating your work. At each time step you check whether the vertex at hand infects others or not, namely you run countSimilarNeigh only for the vertex at hand. Instead you run it for all the neighbors of the vertex. Here is what I think the following code might work well. I have also changed the logic of the code. Now it's focused on the susceptibles and iterate through them. It's faster now but one has to check the results for integrity. My change in the countSimilarNeigh might have also made it a little bit faster.

from igraph import *
from random import *
from time import *

def countSimilarNeigh(g,v):
    return float(g.vs(g.neighbors(v))['state'].count(True))/g.degree(v)

def contagion(g):
    contagious = True
    while contagious:
        for v in g.vs():
            contagious = False
            if v['contagious'] == False:
                if countSimilarNeigh(g,v.index) > 0.1:
                    v['state'] = True
                    v['contagious'] = True
                    contagious = True

def init_graph(n = 60, p = .1):
    g = Graph.Erdos_Renyi(n,p)                
    while g.is_connected == False:
        g = Graph.Erdos_Renyi(n,p)
    g.simplify(multiple=True, loops=True)
    return g


def score(g,repl = 200):
    for c in range(repl):
        cc = 0
        for i in g.vs():
            i['contagious'] = False
            i['state'] = False
            if random() < .1 and cc < 4:
                i['state'] = True
                i['contagious'] = True
                cc += 1
        contagion(g)

t0 = time()    
score(init_graph())
print time()-t0