Fast controlling of rumors with limited cost in social networks

Innumerable rumors spread quickly through social networks and how to fast control the spread of rumors is crucial. An efficient way is to take different measures for users with different influence extent by rumors, but the costs of these measures vary. In this paper, we try to minimize the spread (termination) time of rumors considering the controlling cost. To solve this problem, we creatively design five different measures to control rumors. First, we propose a contact coefficient to quantify the influence weight for each user. Second, we classify the users to different groups based on their influence weights so that the rumors can be controlled by the measures accordingly. Thus, the controlling of rumors can be formulated into an optimization problem, in which decision variables based on contact coefficients are used to classify users. Then an approximation algorithm named WB-GA is designed to classify different users, ensuring that rumors can be controlled as fast as possible within given costs. The experimental results on real online networks show that our algorithm is highly efficient and effective.