Greedy algorithm for viral marketing is good engough

The viral marketing is a very mathematical question. We assume that each client has some probabilities to distribute the information to other places, then we need to calculate the minimum number to ensure that all the network is infected after some time. We can just simplify the question such that we choose a community and then consider its neighborhood. Then a naive method is to find the vertex who will add the most number into the community. Is this method smart enough?

The answer is amazing, Yes! If we do like this, we can achieve a solution that infected the network at least constant times of the optimal solution.

In the following, we list the main steps in the proof. We denote F(A) the number of vertex connected. Then a key formula is 

F(A \union B) + F(A \intersection B) <= F(A) + F(B)

Then, in the stream of greedy algorithm C_i, the increment is not so bad. That is 

F(C_{i+1}) - F(C_i) >= 1\k * (F(C) - F(C_i))

If we change a little this formula, we will get 

F(C) - F(C_i) <= (1 - 1\k)^k * (F(C) - F(0))

So the greedy algorithm attends at least 1 - 1/e = 0.632 times the optimal solution, a result good enough in certain situation. 

OK, greedy algorithm is not always the best but not bad.