Consider a diffusion process that follows the Independent Cascade Model on the g

Question

Consider a diffusion process that follows the Independent Cascade Model on the graph in the figure. Compute the expected number of nodes activated eventually.

3. a (20pt) Consider a diffusion process that follows the Independent Cascade Model on the graph in the below figure. The numbers on an edge (u, v) is the influence probability put, i.e., the probability that v gets activated by u once u becomes active. Assume that initially the seed set S consists of nodes fi, 2). Compute the expected number of nodes activated eventually. 0.5 0.6 0.4 b) (10pt Same as the part b, however, compute the expected number of nodes activated eventually for the following graph and the seed set S' {1). 0.2 0.4 0.3 0.5 0.6

Explanation / Answer

In Independent Cascade Model :

When a node v becomes active, it gets one chance of activating each currently inactive neighbor w.

This activation happens with a probability pvw as marked on the diretced edges from v to w .

Monotonicity : Active nodes never deactivate and hence no second attempt is made to activate them .

The IC model is submodular in nature and is used for Influence maximization problem to trigger a large cascade of influence (e.g. further adoptions of a product , ideas , information etc. )

Given k (budget), find a k-node set S to maximize f(S) which is NP-Hard

Greedy maximization algorithm returns near-optimal solution .

a. As we already have node 1 and 2 activated and node 1 has higher probability ( 0.5 >0.4) of activating node 3 .

Nodes eventually active :

3 nodes get activated eventually with a probability of 0.5

4th node is activated by node 3 with 0.6 probability therefore the factor becomes 0.5*0.6 = 0.3 .

Therefore :

4 nodes get activated eventually with a probability of 0.3

b. Similarly starting with node 1

2 nodes get activated eventually with a probability of 0.5 i.e. nodes ( 1,3 )

3 nodes get activated eventually with a probability of 0.3 ( 0.5 * 0.6 ) i.e. nodes ( 1,3,4 ) In order 1 ->3 -> 4

4 nodes get activated eventually with a probability of 0.072 ( 0.4 *0.3 * 0.6 ) i.e. nodes ( 1,2,3,4 ) In order 1 ->2 -> 3 -> 4

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.