Home »
Academic Articles »
Algorithm »
Spreading Social Influence with both Positive and Negative Opinions in Online Networks
Spreading Social Influence with both Positive and Negative Opinions in Online Networks
Jing (Selena) He
(<institution content-type="dept">College of Computing and Software Engineering</institution> at <institution>Kennesaw State University</institution>, <city>Kennesaw</city>, <state>GA</state> <postal-code>30144</postal-code>, <country>USA</country>.)
Meng Han
(<institution content-type="dept">College of Computing and Software Engineering</institution> at <institution>Kennesaw State University</institution>, <city>Kennesaw</city>, <state>GA</state> <postal-code>30144</postal-code>, <country>USA</country>.)
Shouling Ji
(<institution>Department of Computer Science at Zhejiang University</institution>, <city>Hangzhou</city> <postal-code>310058</postal-code>, <country>China</country>.)
Tianyu Du
(<institution>Department of Computer Science at Zhejiang University</institution>, <city>Hangzhou</city> <postal-code>310058</postal-code>, <country>China</country>.)
Zhao Li
(<institution>Alibaba Group</institution>, <city>Hangzhou</city> <postal-code>310052</postal-code>, <country>China</country>.)
Journal: Big Data Mining and Analytics
•
• Tsinghua University Press
• ISSN: 2096-0654
Abstract
Social networks are important media for spreading information, ideas, and influence among individuals. Most existing research focuses on understanding the characteristics of social networks, investigating how information is spread through the "word-of-mouth" effect of social networks, or exploring social influences among individuals and groups. However, most studies ignore negative influences among individuals and groups. Motivated by the goal of alleviating social problems, such as drinking, smoking, and gambling, and influence-spreading problems, such as promoting new products, we consider positive and negative influences, and propose a new optimization problem called the Minimum-sized Positive Influential Node Set (MPINS) selection problem to identify the minimum set of influential nodes such that every node in the network can be positively influenced by these selected nodes with no less than a threshold of θ. Our contributions are threefold. First, we prove that, under the independent cascade model considering 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, we conduct extensive simulations and experiments on random graphs and seven different real-world data sets that represent small-, medium-, and large-scale networks.
Jing (Selena) He, Meng Han, Shouling Ji, et al. (2019). "Spreading Social Influence with both Positive and Negative Opinions in Online Networks". Big Data Mining and Analytics. https://doi.org/10.26599/bdma.2018.9020034