3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ I'm not sure I can follow the problem from your code. From your naming, it seems like seed contains the nodes informed at t = 0 and that diffusion_time is the time it takes the information to go from u to v. Hence, we infer that the time to inform v is informed_nodes[u] + diffusion_time, and that for each seed s, informed_time[s] == 0. This is different in your code, did I misunderstand the problem? \$\endgroup\$ – 301_Moved_Permanently Aug 21 '20 at 20:45
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Using the math.nan and math.inf constants are preferable over using float("...") to repeatedly convert strings into the special floating point singleton values. \$\endgroup\$ – AJNeufeld Aug 22 '20 at 21:14
  • \$\begingroup\$ @AJNeufeld You are right. I did not know of this convention, but it makes sense to not constantly arse a string... \$\endgroup\$ – Graipher Aug 23 '20 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.