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

7.2 Information Cascades 191

Algorithm 7.2Maximizing the spread of cascades – Greedy algorithm

Require:Diffusion graphG(V,E), budgetk

1: return Seed setS(set of initially activated nodes)

2: i=0;

3: S={};

4: whilei =kdo

5: v=arg maxv∈V\Sf(S∪{v});

or equivalentlyarg maxv∈V\Sf(S∪{v})−f(s)

6: S=S∪{v};

7: i=i+1;

8: end while

9: ReturnS;

Theorem 7.1.Kempe et al. [2003] Let f be a (1) non-negative, (2) mono-

tone, and (3) submodular set function. Construct k-element set S, each time

by adding nodev, such that f(S∪{v})(or equivalently, f(S∪{v})−f(s))

is maximized. Let SOptimalbe the k-element set such that f is maximized.

Then f(S)≥(1−^1 e)f(SOptimal).

This theorem states that by constructing the setSgreedily one can get at

least a (1− 1 /e)≈63% approximation of the optimal value. Algorithm7.2

details this greedy approach. The algorithm starts with an empty setSand

adds nodev 1 , which ultimately activates most other nodes if activated. For-

mally,v 1 is selected such thatf({v 1 }) is the maximum. The algorithm then

selects the second nodev 2 such thatf({v 1 ,v 2 }) is maximized. The process

is continued until thekthnodevkis selected. Following this algorithm,

we find an approximately reasonable solution for the problem of cascade

maximization.

Example 7.3.For the following graph, assume that node i activates node

j when|i−j|≡2(mod3). Solve cascade maximization for k= 2.

4

32

5

6 1