Influence Spread in Social Networks with both Positive and Negative Influences

摘要

Social networks are important mediums for spreading information, ideas, and influences among individuals. Most of existing research works of social networks focus on understanding the characteristics of social networks and spreading information through the "word of mouth" effect. However, most of them ignore negative influences among individuals and groups. Motivated by alleviating social problems, such as drinking, smoking, gambling, and influence spreading problems such as promoting new products, we take both positive and negative influences into consideration and propose a new optimization problem, named the Minimum-sized Positive Influential Node Set (MPINS) selection, to identify the minimum set of influential nodes, such that every node in the network can be positively influenced by these selected nodes no less than a threshold θ. Our contributions are threefold. First, we prove that, under the independent cascade model considering both positive and negative influences, MPINS is APX-hard. Subsequently, we present a greedy approximation algorithm to address the MPINS selection problem. Finally, to validate the proposed greedy algorithm, extensive simulations and experiments are conducted on random Graphs and seven different real-world data sets representing small, medium, and large scale networks.