# Independent cascade model for networkx graphs

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

• 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? – 301_Moved_Permanently Aug 21 '20 at 20:45

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.

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.

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