Spreading Social Influence with both Positive and Negative Opinions in Online Networks

作     者：Jing (Selena) He Meng Han Shouling Ji Tianyu Du Zhao Li 

作者机构：College of Computing and Software Engineering at Kennesaw State University Department of Computer Science at Zhejiang University Alibaba Group 

出 版 物：《Big Data Mining and Analytics》 (大数据挖掘与分析（英文）)

年 卷 期：2019年第2卷第2期

页      面：100-117页

核心收录：

学科分类：0810[工学-信息与通信工程] 1205[管理学-图书情报与档案管理] 08[工学] 0839[工学-网络空间安全] 0804[工学-仪器科学与技术] 080402[工学-测试计量技术及仪器] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：funded in part by the Kennesaw State University College of Science and Mathematics Interdisciplinary Research Opportunities (IDROP) Program the Provincial Key Research and Development Program of Zhejiang, China (No. 2016C01G2010916) the Fundamental Research Funds for the Central Universities, the Alibaba-Zhejiang University Joint Research Institute for Frontier Technologies (A.Z.F.T.) (No. XT622017000118) the CCF-Tencent Open Research Fund (No. AGR20160109). 

主　　题：influence spread social networks positive influential node set greedy algorithm positive and negative influences 

摘      要：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 realworld data sets that represent small-, medium-, and large-scale networks.