Journal Home > Volume 2 , issue 2

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.


menu
Abstract
Full text
Outline
About this article

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

Show Author's information Jing (Selena) He( )Meng HanShouling JiTianyu DuZhao Li
College of Computing and Software Engineering at Kennesaw State University, Kennesaw, GA 30144, USA.
Department of Computer Science at Zhejiang University, Hangzhou 310058, China.
Alibaba Group, Hangzhou 310052, China.

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.

Keywords:

influence spread, social networks, positive influential node set, greedy algorithm, positive and negative influences
Received: 20 July 2018 Accepted: 19 September 2018 Published: 21 May 2019 Issue date: June 2019
References(48)
[1]
D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in Proc. of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, pp. 137-146.
[2]
K. Saito, M. Kimura, and H. Motoda, Discovering influential nodes for sis models in social networks, in Proc. International Conference on Discovery Science, 2009, pp. 302-316.
[3]
Y. Li, W. Chen, Y. Wang, and Z. Zhang, Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships, in Proc. of the Sixth ACM International Conference on Web Search and Data Mining, 2013, pp. 657-666.
[4]
M. Han, M. Yan, Z. Cai, Y. Li, X. Cai, and J. Yu, Influence maximization by probing partial communities in dynamic online social networks, Transactions on Emerging Telecommunications Technologies, vol. 28, no. 4, p. e3054, 2016.
[5]
X. He, G. Song, W. Chen, and Q. Jiang, Influence blocking maximization in social networks under the competitive linear threshold model, in Proc. of the 2012 SIAM International Conference on Data Mining, 2012, pp. 463-474.
[6]
W. Lu, F. Bonchi, A. Goyal, and L. V. Lakshmanan, The bang for the buck: Fair competitive viral marketing from the host perspective, in Proc. of the 19th SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013, pp. 928-936.
[7]
F. Wang, H. Du, E. Camacho, K. Xu, W. Lee, Y. Shi, and S. Shan, On positive influence dominating sets in social networks, Theoretical Computer Science, vol. 412, no. 3, pp. 265-269, 2011.
[8]
M. Han and Y. Li, Influence analysis: A survey of the state-of-the-art, in International Symposium on Bioinformatics Research and Applications, 2018, pp. 259-264.
[9]
J. Tang, J. Sun, C. Wang, and Z. Yang, Social influence analysis in large-scale networks, in Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009, pp. 807-816.
[10]
A. Goyal, F. Bonchi, and L. V. Lakshmanan, Learning influence probabilities in social networks, in Proc. of the Third ACM International Conference on Web Search and Data Mining, 2010, pp. 241-250.
[11]
C. Wang, J. Tang, J. Sun, and J. Han, Dynamic social influence analysis through time-dependent factor graphs, in Proc. Advances in Social Networks Analysis and Mining (ASONAM), 2011 International Conference on, 2011, pp. 239-246.
[12]
M. Han, L. Li, Y. Xie, J. Wang, Z. Duan, J. Li, and M. Yan, Near-complete privacy protection: Cognitive optimal strategy in location-based services, Procedia Computer Science, vol. 129, pp. 298-3047, 2018.
[13]
L. Liu, M. Han, Y. Zhou, and Y. Wang, LSTM recurrent neural networks for influenza trends prediction, in International Symposium on Bioinformatics Research and Applications, 2018, pp. 259-264.
[14]
H. Albinali, M. Han, J. Wang, H. Gao, and Y. Li, The roles of social network mavens, in Proc. of the 12th International Conference on Mobile Ad-hoc and Sensor Networks, 2016.
[15]
M. Han, M. Yan, J. Li, S. Ji, and Y. Li, Generating uncertain networks based on historical network snapshots, in Proc. COCOON, 2013, pp.747-758.
[16]
A. Goyal, W. Lu, and L. V. Lakshmanan, Celf++: Optimizing the greedy algorithm for influence maximization in social networks, in Proc. of the 20th International Conference Companion on World Wide Web, 2011, pp. 47-48.
[17]
M. Han, M. Yan, Z. Cai, and Y. Li, An exploration of broader influence maximization in timeliness networks with opportunistic selection, Journal of Network and Computer Applications, vol. 63, pp. 39-49, 2016.
[18]
L. Cui, H. Hu, S. Yu, Q. Yan, Z. Ming, Z. Wen, and N. Lu, A novel evolutionary algorithm based on degree descending search strategy for influence maximization in social networks, Journal of Network and Computer Applications, vol. 103, pp. 119-130, 2018.
[19]
C. Wang, W. Chen, and Y. Wang, Scalable influence maximization for independent cascade model in largescale social networks, Data Mining and Knowledge Discovery, vol. 25, no. 3, p. 545, 2012.
[20]
M. Han, Z. Duan, C. Ai, F. W. Lybarger, Y. Li, and A. G. Bourgeois, Time constraint influence maximization algorithm in the age of big data, International Journal of Computational Science and Engineering, vol. 15, nos. 3&4, p. 165, 2017.
[21]
F. Lu, W. Zhang, L. Shao, X. Jiang, P. Xu, and H. Jin, Scalable influence maximization under independent cascade model, Journal of Network and Computer Applications, vol. 86, pp. 15-23, 2017.
[22]
J. Tang, S. Wu, and J. Sun, Confluence: Conformity influence in large social networks, in Proc. of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013, pp. 347-355.
[23]
K. Saito, R. Nakano, and M. Kimura, Prediction of information diffusion probabilities for independent cascade model, in Proc. International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, 2008, pp. 67-75.
[24]
M. Han, M. Yan, J. Li, S. Ji, and Y. Li, Neighborhood-based uncertainty generation in social networks, Journal of Combinatorial Optimization, vol. 28, no. 3, pp. 561-576, 2014.
[25]
M. Han, J. Wang, Z. Duan, M. Yan, C. Ai, and Z. Hong, Near-complete privacy protection: Cognitive optimal strategy in location-based services, in Proc. of the International Conference on Identification, Information and Knowledge in the Internet of Things. Qufu, China, 2017.
[26]
F. Wang, E. Camacho, and K. Xu, Positive influence dominating set in online social networks, in Proc. International Conference on Combinatorial Optimization and Applications, 2009, pp. 313-321.
[27]
X. Zhu, J. Yu, W. Lee, D. Kim, S. Shan, and D. Z. Du, New dominating sets in social networks, Journal of Global Optimization, vol. 48, no. 4, pp. 633-642, 2010.
[28]
J. S. He, S. Ji, R. Beyah, and Z. Cai, Minimum-sized influential node set selection for social networks under the independent cascade model, in Proc. of the 15th ACM International Symposium on Mobile Ad hoc Networking and Computing, 2014, pp. 93-102.
[29]
P. Domingos and M. Richardson, Mining the network value of customers, in Proc. of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 57-66.
[30]
M. Richardson and P. Domingos, Mining knowledgesharing sites for viral marketing, in Proc. of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, pp. 61-70.
[31]
D. Kempe, J. Kleinberg, and É. Tardos, Influential nodes in a diffusion model for social networks, in Proc. International Colloquium on Automata, Languages, and Programming, 2005, pp.1127-1138.
[32]
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, in Proc. of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 420-429.
[33]
W. Chen, Y. Yuan, and L. Zhang, Scalable influence maximization in social networks under the linear threshold model, in Proc. Data Mining (ICDM), 2010 IEEE 10th International Conference on, 2010, pp. 88-97.
[34]
W. Chen, C. Wang, and Y. Wang, Scalable influence maximization for prevalent viral marketing in large-scale social networks, in Proc. of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010, pp. 1029-1038.
[35]
J. Li, Z. Cai, J. Wang, M. Han, and Y. Li, Truthful incentive mechanisms for geographical position conflicting mobile crowd sensing systems, IEEE Transactions on Computational Social Systems, vol. 5, no. 2. pp. 324-334, 2018.
[36]
M. Han, J. Li, Z. Cai, and Q. Han, Privacy reserved influence maximization in gps-enabled cyber-physical and online social networks, in Proc. SocialCom 2016, 2016, pp. 284-292.
[37]
M. Han, L. Li, Y. Xie, J. Wang, Z. Duan, J. Li, and M. Yan, Cognitive approach for location privacy protection, IEEE Access, vol. 6, pp. 13466-13477, 2018.
[38]
A. Goyal, F. Bonchi, and L. V. Lakshmanan, A data based approach to social influence maximization, Proc. of the VLDB Endowment, vol. 5, no. 1, pp. 73-84, 2011.
[39]
F. Zou, Z. Zhang, and W. Wu, Latency-bounded minimum influential node selection in social networks, in Proc. International Conference on Wireless Algorithms, Systems, and Applications, 2009, pp. 519-526.
[40]
F. Zou, J. K. Willson, Z. Zhang, and W. Wu, Fast information propagation in social networks, Discrete Mathematics, Algorithms and Applications, vol. 2, no. 1, pp. 125-141, 2010.
[41]
P. Zhang, W. Chen, X. Sun, Y. Wang, and J. Zhang, Minimizing seed set selection with probabilistic coverage guarantee in a social network, in Proc. of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014, pp. 1306-1315.
[42]
D. Z. Du and K. I. Ko, Theory of Computational Complexity. John Wiley & Sons, 2011.
[43]
J. Leskovec, L. A. Adamic, and B. A. Huberman, The dynamics of viral marketing, ACM Transactions on the Web (TWEB), vol. 1, no. 1, p. 5, 2007.
[44]
J. Leskovec, D. Huttenlocher, and J. Kleinberg, Predicting positive and negative links in online social networks, in Proc. of the 19th International Conference on World Wide Web, 2010, pp. 641-650.
[45]
J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, Arnetminer: Extraction and mining of academic social networks, in Proc. of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008, pp. 990-998.
[46]
J. Hopcroft, T. Lou, and J. Tang, Who will follow you back?: Reciprocal relationship prediction, in Proc. of the 20th ACM International Conference on Information and Knowledge Management, 2011, pp. 1137-1146.
[47]
T. Lou, J. Tang, J. Hopcroft, Z. Fang, and X. Ding, Learning to predict reciprocity and triadic closure in social networks, ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 7, no. 2, p. 5, 2013.
[48]
C. Wang, W. Chen, and Y. Wang, Scalable influence maximization for independent cascade model in largescale social networks, Data Mining and Knowledge Discovery, vol. 25, no. 3, pp. 545-576, 2012.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 20 July 2018
Accepted: 19 September 2018
Published: 21 May 2019
Issue date: June 2019

Copyright

© The author(s) 2019

Acknowledgements

This research was 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), and the CCF-Tencent Open Research Fund (No. AGR20160109).

Rights and permissions

Reprints and Permission requests may be sought directly from editorial office.

Return