Minimum-Cost Information Dissemination in Social Networks

In a social network, when the number of users discussing a topic exceeds a critical threshold, the topic will have a serious impact on the corresponding community. In this paper, we consider the problem of finding the minimum set of initial users of a topic to propagate a message so that, with a given guaranteed probability, the number of users discussing the topic would reach the critical threshold. This study is formally called the Minimum-Cost Information Dissemination (MCID) problem in our research. Different from the influence maximization problem, the MCID problem attempts to achieve influence maximization from the minimum cost perspective. To tackle the problem, we proposed a novel method based on h-hop independent set, HISS. Based on the independent set, HISS guarantees that the source nodes are sparsely distributed in the network. In addition, since HISS utilizes h-hop graph transformation, it can reduce the number of source nodes and avoid the scenarios in which the source nodes have common neighbors. The proposed method was evaluated with two real networks. The experimental results indicate that our proposed algorithm outperforms the state-of-the-art algorithms.