Social Media Mining: An Introduction

P1: qVa Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-07 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:17

188 Information Diffusion in Social Media

Algorithm 7.1Independent Cascade Model (ICM)

Require: Diffusion graphG(V,E), set of initial activated nodesA 0 , acti-

vation probabilitiespv,w

1: return Final set of activated nodesA∞

2: i=0;

3: whileAi ={}do

4:

5: i=i+1;

6: Ai={};

7: for allv∈Ai− 1 do

8: for allwneighbor ofv,w /∈∪ij= 0 Ajdo

9: rand=generate a random number in [0,1];

10: ifrand<pv,wthen

11: activatew;

12: Ai=Ai∪{w};

13: end if

14: end for

15: end for

16: end while

17: A∞=∪ij= 0 Aj;

18: ReturnA∞;

undirected, for any two vertices connected via an edge, there is an equal

chance of one activating the other. Consider the network in step 1. The

values on the edges denote pv,w’s. The ICM procedure starts with a set of

nodes activated. In our case, it is nodev 1. Each activated node gets one

chance of activating its neighbors. The activated node generates a random

number for each neighbor. If the random number is less than the respective

pv,wof the neighbor (see Algorithm7.1, lines 9–11), the neighbor gets acti-

vated. The random numbers generated are shown in Figure7.4in the form

of inequalities, where the left-hand side is the random number generated

and the right-hand side is the pv,w. As depicted, by following the procedure

after five steps, five nodes get activated and the ICM procedure converges.

Clearly, the ICM characterizes an information diffusion process.^2 It

is sender-centered, and once a node is activated, it aims to activate all its

neighboring nodes. Node activation in ICM is a probabilistic process. Thus,

we might get different results for different runs.