使用 iGraph 的最快可能传染算法

Question

我正在尝试编写一个传染算法：

创建 igraph 图
用火点亮四个随机节点（状态 = 真）
如果至少 10% 的邻居着火，则将火势蔓延到另一个节点。传播火势的节点耗尽 (state = False)
当没有节点着火时停止。

到目前为止，这是我的代码：

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() 使用了最多的资源：

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

我认为你在重复你的工作。在每个时间步，您检查手头的顶点是否感染其他顶点，即您运行 countSimilarNeigh 仅针对手头的顶点。相反，您运行它用于顶点的所有邻居。这是我认为以下代码可能运行良好的地方。我还更改了代码的逻辑。现在它专注于易感者并对其进行迭代。现在速度更快，但必须检查结果的完整性。我对 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

使用 iGraph 的最快可能传染算法

Fastest possible contagion algorithm with iGraph

python

igraph