1
$\begingroup$

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)
$\endgroup$

1 Answer 1

1
$\begingroup$

If A is following B, then A has an OUT edge to B, that's right.

However, I agree it is not intuitive, since in the case of twitter the propagation of information goes from B to A. It is ok, provided you take into account that there is no propagation probability for out edges; i.e. you can influence your followers, but not the people you are following.

Thus, for the propagation you should use G.in_edges (that's in networkx, I haven't used iGraph but in the docs I see it should be G.predecessors). G.sucessors would give all the neighbors in networkx, nodes with both in and out edges; in iGraph, however, it gives only out edges. (Confusing!)

It is true that in the original code you provide it uses G.sucessors, i.e. all the neighbors in networkx. Do you have any context for that code, when it was used?

This is another piece of code, but this one if for twitter. Unfortunately it is in java but you can see it uses G.in_edges. But the algorithm is also described in English,

Each node is evaluated as per the following steps, 
1. Push it to the stack
2. while stack is not empty
2.1 pop the node (v) from stack
2.2 consider it as active and put it into active sec
2.3 Repeat following for each **inbound neighbor** (u) of node
2.3.1 generate a random floating point number (rand) between 0 to 1.
2.3.2 if (propagation_probability(u, v)  <  rand)
2.3.2.1 if (u is not in active set) push u to stack

Hope it helps.

EDIT: After comments, I add my very simple code for the implementation using networkx. Of course, any feedback would be more than welcome. The algorithm itself is debugged, however I must say I am still trying to figure out better ways for the following:

  • setting the probabilities for the propagation of each of the users
  • validating the results
  • how good the retweets are a proxy for the structure of the network (since downloading the followers is too slow due to Twitter's rate limits)

This is the method for the diffusion,

def single_diffusion(G, seeds, tot_users, debug=False):
    targets = list()
    actives = set()
    results = {}

    for seed in seeds:
        targets.append(seed)
        actives.add(seed)
        while True:
            target = targets.pop()
            if debug:
                print("t", target)
            for follower, u in G.in_edges(target):
                if debug:
                    print("f", len(actives), follower)
                    print(G[follower][target]['weight'])
                if random.random() < tot_users.loc[follower, 'p']:
                    if follower not in actives:
                        if debug:
                            print("a", len(actives), follower)
                        actives.add(follower)
                        targets.append(follower)
            if len(targets) == 0:
                if debug:
                    print("number of actives: ", len(actives))
                results[seed] = len(actives)
                break
            if len(actives) > len(tot_users):
                raise RuntimeError("infinite loop!")

    return results

where tot_users is a dataframe for all the users in the graph, and contains a column for the probability of distribution.

The loop for the results, and an example for calculating the mean.

results = {}
for i in range(num_iter):
    new_results = single_diffusion(G, seeds)
    if results != {}:
        for k,v in new_results.items():
            results[k] = results[k] + [v]
    else:
        for k,v in new_results.items():
            results[k] = [v]

for k,v in results.items():
    print(k)
    print(np.mean(results[k]))
$\endgroup$
4
  • $\begingroup$ I have do that in java as well. Can you provide the source code? $\endgroup$
    – toy
    Sep 16, 2015 at 13:29
  • $\begingroup$ I meant that the link provides code in java. Well, it's kind of pseudo-code I guess. I'm working in python with networkx. However, I'm not using information from followers (rest api is too slow to get them for a big enough number of users), I'm using info from retweets to build the graph, but still not sure about the results, honestly! $\endgroup$
    – lrnzcig
    Sep 16, 2015 at 13:36
  • $\begingroup$ Ok, the code too dirty to post it right now, but I will post it by the end of the week (i.e. the part that corresponds to the algorithm) $\endgroup$
    – lrnzcig
    Sep 16, 2015 at 17:07
  • $\begingroup$ Done. Hope it helps. $\endgroup$
    – lrnzcig
    Sep 18, 2015 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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