基于iGraph的最快可能传染算法

Question

我试图写一个传染算法：

1. 创建igraph图形
2. 例如，使用一个fire（state=True）来初始化四个随机节点
3. 如果至少有10%的邻居着火，则会将火蔓延到另一个节点。传播其耗尽的火焰的节点（state=False）
4. 没有节点着火时停止。在

以下是我目前为止的代码：

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

不幸的是，它在我的电脑上运行得很慢，我需要计算大量的复制。有没有一种方法可以优化这段代码，或者使用不同的方法以更有效的方式执行传染？在

我把这个算法基于http://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/

编辑：用cprofiler运行可以提供更多信息。countSimilarNeigh（）使用的资源最多，目前：

^{pr2}$

Answer 1

我想你在重复你的工作。在每一步中，你都要检查手头的顶点是否感染了其他顶点，也就是说，你只对手头的顶点运行countSimilarNeigh。而是对顶点的所有邻居运行它。下面是我认为下面的代码可能会很好地工作。我也改变了代码的逻辑。现在，它集中在易感对象上，并对其进行迭代。现在速度更快了，但必须检查结果的完整性。我的改变也可能让它快了一点。在

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