Spreading Social Influence with both Positive and Negative Opinions in Online Networks
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 e...
Saved in:
Main Authors: | , , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Tsinghua University Press
2019-06-01
|
Series: | Big Data Mining and Analytics |
Subjects: | |
Online Access: | https://www.sciopen.com/article/10.26599/BDMA.2018.9020034 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
_version_ | 1832568886684286976 |
---|---|
author | Jing (Selena) He Meng Han Shouling Ji Tianyu Du Zhao Li |
author_facet | Jing (Selena) He Meng Han Shouling Ji Tianyu Du Zhao Li |
author_sort | Jing (Selena) He |
collection | DOAJ |
description | 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. |
format | Article |
id | doaj-art-005bac0d78514faaae1f5aabf6ddfb0d |
institution | Kabale University |
issn | 2096-0654 |
language | English |
publishDate | 2019-06-01 |
publisher | Tsinghua University Press |
record_format | Article |
series | Big Data Mining and Analytics |
spelling | doaj-art-005bac0d78514faaae1f5aabf6ddfb0d2025-02-02T23:47:57ZengTsinghua University PressBig Data Mining and Analytics2096-06542019-06-012210011710.26599/BDMA.2018.9020034Spreading Social Influence with both Positive and Negative Opinions in Online NetworksJing (Selena) He0Meng Han1Shouling Ji2Tianyu Du3Zhao Li4<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>.<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>.<institution>Department of Computer Science at Zhejiang University</institution>, <city>Hangzhou</city> <postal-code>310058</postal-code>, <country>China</country>.<institution>Department of Computer Science at Zhejiang University</institution>, <city>Hangzhou</city> <postal-code>310058</postal-code>, <country>China</country>.<institution>Alibaba Group</institution>, <city>Hangzhou</city> <postal-code>310052</postal-code>, <country>China</country>.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.https://www.sciopen.com/article/10.26599/BDMA.2018.9020034influence spreadsocial networkspositive influential node setgreedy algorithmpositive and negative influences |
spellingShingle | Jing (Selena) He Meng Han Shouling Ji Tianyu Du Zhao Li Spreading Social Influence with both Positive and Negative Opinions in Online Networks Big Data Mining and Analytics influence spread social networks positive influential node set greedy algorithm positive and negative influences |
title | Spreading Social Influence with both Positive and Negative Opinions in Online Networks |
title_full | Spreading Social Influence with both Positive and Negative Opinions in Online Networks |
title_fullStr | Spreading Social Influence with both Positive and Negative Opinions in Online Networks |
title_full_unstemmed | Spreading Social Influence with both Positive and Negative Opinions in Online Networks |
title_short | Spreading Social Influence with both Positive and Negative Opinions in Online Networks |
title_sort | spreading social influence with both positive and negative opinions in online networks |
topic | influence spread social networks positive influential node set greedy algorithm positive and negative influences |
url | https://www.sciopen.com/article/10.26599/BDMA.2018.9020034 |
work_keys_str_mv | AT jingselenahe spreadingsocialinfluencewithbothpositiveandnegativeopinionsinonlinenetworks AT menghan spreadingsocialinfluencewithbothpositiveandnegativeopinionsinonlinenetworks AT shoulingji spreadingsocialinfluencewithbothpositiveandnegativeopinionsinonlinenetworks AT tianyudu spreadingsocialinfluencewithbothpositiveandnegativeopinionsinonlinenetworks AT zhaoli spreadingsocialinfluencewithbothpositiveandnegativeopinionsinonlinenetworks |