Independent cascade model for networkx graphs

Question

Similar to this question, I implemented the independent cascade model, but for a given networkx graph (including multigraph with parallel edges). My focus is on readability, pythonic-ness, and performance (although the problem itself is NP-hard).

I cannot wait to hear your feedback!

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

Correctness / Readability

I'm not sure if this is a bug, or just an unclearness of the algorithm.

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

If you want to loop over the edges, until no change is made, then the updated = False looks like it is in the wrong place. As it currently stands, if the last edge processed in the for loop fails any of the 3 if conditions, the updated flag is set to False, even if a prior edge set it to True.

Wouldn't the correct implementation be:

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

Now, for each while loop iteration, we start by clearing the flag. Then, if any edge results in updated = True, a change has been made and the while loop is repeated.

If the updated = False was in the correct place, then the readability of the code could be improved with comments explaining why update = True only matters for the last edge returned by the for loop.

Answer 2

You should not use ==/!= to compare to singletons like None, instead use is/is not.

Here is one way to restructure your conditions. This reduces the amount of nesting, which hopefully increases the overall readability.

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

Here I also used dict.get with the optional default argument set in such a way that the conditions are the right way around for missing data.

>>> 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

Just make sure you don't run into math.inf > math.inf -> False or math.inf > math.nan -> False

You should also add a docstring to your function explaining what it does and what the arguments are.