网络图的独立级联模型

Question

类似于这个问题，我实现了独立的级联模型，但是对于给定的网络图(包括具有并行边的多个图)。我的重点是可读性，丙酮-性，和性能(虽然问题本身是NP-困难)。

我等不及要听到你的反馈了！

def independent_cascade_model(G: nx.Graph, seed: list, beta: float=1.0):       
    informed_nodes = {n: None for n in seed}
    updated = True

    while updated:
        for u, v, diffusion_time in G.edges(nbunch=informed_nodes, data='diffusion_time'):
            updated = False
            if informed_nodes[u] == None or informed_nodes[u] < diffusion_time:
                if random.random() < beta:
                    if v not in informed_nodes or diffusion_time < informed_nodes[v]:
                        informed_nodes[v] = diffusion_time
                        updated = True
    return informed_nodes

Answer 1

正确性/可读性

我不确定这是一个错误，还是只是算法的不清晰。

    while updated:
        for ... in ...:
            updated = False
            if ...:
                if ...:
                    if ...:
                        ...
                        updated = True

如果您想在边缘上循环，直到没有进行任何更改，那么updated = False看起来是在错误的位置。按照目前的情况，如果在for循环中处理的最后一个边缘失败了，则updated标志被设置为False，即使先前的边缘将其设置为True。

正确的实现不是：

    while updated:
        updated = False
        for ... in ...:
            if ...:
                if ...:
                    if ...:
                        ...
                        updated = True

现在，对于每个while循环迭代，我们从清除标志开始。然后，如果在updated = True中产生任何边，则进行更改，并重复while循环。

如果updated = False位于正确的位置，那么可以通过注释来提高代码的可读性，解释为什么update = True只对for循环返回的最后边缘很重要。

Answer 2

您不应该使用==/!=来与None这样的单例进行比较，而应该使用is/is not。

这里有一种方法来重组你的条件。这减少了嵌套的数量，这有望提高整体可读性。

import math

def independent_cascade_model(G: nx.Graph, seed: list, beta: float=1.0):       
    informed_nodes = {n: None for n in seed}
    updated = True
    while updated:
        updated = False
        for u, v, diffusion_time in G.edges(nbunch=informed_nodes, data='diffusion_time'):
            if informed_nodes.get(u, math.nan) <= diffusion_time:
                # node is already set up properly
                continue
            elif random.random() >= beta:
                continue
            elif informed_nodes.get(v, math.inf) > diffusion_time:
                informed_nodes[v] = diffusion_time
                updated = True
    return informed_nodes

在这里，我还在可选的默认参数集中使用了dict.get，这种方式使得条件是处理丢失数据的正确方法。

>>> n = 10             # works for any numeric n
>>> math.nan <= n    
# False

>>> import sys
>>> n = sys.maxsize    # works for any numeric n except for inf
>>> math.inf > n
# True

确保你没有遇到math.inf > math.inf -> False或math.inf > math.nan -> False

您还应该向函数中添加一个文档串，解释它所做的事情以及参数是什么。