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
seed
contains the nodes informed att = 0
and thatdiffusion_time
is the time it takes the information to go fromu
tov
. Hence, we infer that the time to informv
isinformed_nodes[u] + diffusion_time
, and that for each seeds
,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