I'm trying to run Independent Cascade Model for my Twitter graph to see who I have to stimulate to get the maximum cascade. This code is inspired by http://php.scripts.psu.edu/hxc249/code_segments/independent_cascade.py which uses Networkx. However, I modified a bit to be able to run with iGraph.
I create my network just OUT degree which corresponds to who I follow in Twitter. However, as far as I understand in order for a node to get infected, that node has to see the information. For example, only my followers would see that I tweeted something and if that node decided to retweeted my status that means the node is infected and the followers of that node can keep retweeting.
So, should I build my graph based on my followers instead of who I follow?
So, if I use
G.successors(mynode) that would be all the nodes that potentially might be infected of the tweet I tweeted?
Here's my code
def independent_cascade_igraph(G, seeds, steps=0): # init activation probabilities for e in G.es(): if 'act_prob' not in e.attributes(): e['act_prob'] = 0.1 elif e['act_prob'] > 1: raise Exception("edge activation probability:", e['act_prob'], "cannot be larger than 1") # perform diffusion A = copy.deepcopy(seeds) # prevent side effect if steps <= 0: # perform diffusion until no more nodes can be activated return _diffuse_all(G, A) # perform diffusion for at most "steps" rounds return _diffuse_k_rounds(G, A, steps) def _diffuse_k_rounds(G, A, steps): tried_edges = set() layer_i_nodes = [ ] layer_i_nodes.append([i for i in A]) while steps > 0 and len(A) < G.vcount(): len_old = len(A) (A, activated_nodes_of_this_round, cur_tried_edges) = _diffuse_one_round(G, A, tried_edges) layer_i_nodes.append(activated_nodes_of_this_round) tried_edges = tried_edges.union(cur_tried_edges) if len(A) == len_old: break steps -= 1 return layer_i_nodes def _diffuse_one_round(G, A, tried_edges): activated_nodes_of_this_round = set() cur_tried_edges = set() for s in A: for nb in G.successors(s): if nb in A or (s, nb) in tried_edges or (s, nb) in cur_tried_edges: continue if _prop_success(G, s, nb): activated_nodes_of_this_round.add(nb) cur_tried_edges.add((s, nb)) activated_nodes_of_this_round = list(activated_nodes_of_this_round) A.extend(activated_nodes_of_this_round) return A, activated_nodes_of_this_round, cur_tried_edges def _prop_success(G, src, dest): ''' act_prob = 0.1 for e in G.es(): if (src, dest) == e.tuple: act_prob = e['act_prob'] break ''' return random.random() <= 0.1 independent_cascade_igraph(twitter_igraph, ['121817564'], steps=1)