Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate

By Alex Collins, Rachel Cummings, T. Ke, Zhenming Liu, David Rincón, Xiaorui Sun, Yajun Wang, Wei Wei, Yifei Yuan. SDM, 2011

417 citations recorded by the source corpus.

Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. In this paper, we propose an extension to the independent cascade model that incorporates the emergence and propagation of negative opinions. The new model has an explicit parameter called quality factor to model the natural behavior of people turning negative to a product due to product defects. Our model incorporates negativity bias (negative opinions usually dominate over positive opinions) commonly acknowledged in the social psychology literature. The model maintains some nice properties such as submodularity, which allows a greedy approximation algorithm for maximizing positive influence within a ratio of 1-1/e. We define a quality sensitivity ratio (qs-ratio) of influence graphs and show a tight bound of T(vn/k) on the qs-ratio, where n is the number of nodes in the network and k is the number of seeds selected, which indicates that seed selection is sensitive to the quality factor for general graphs. We design an efficient algorithm to compute influence in tree structures, which is nontrivial due to the negativity bias in the model. We use this algorithm as the core to build a heuristic algorithm for influence maximization for general graphs. Through simulations, we show that our heuristic algorithm has matching influence with a standard greedy approximation algorithm while being orders of magnitude faster.

Subfields: Information Systems, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/0b5900a1a3cc3fabba8b4aa516e761bf6c1e8f88

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

1. Kyomin Jung
2. Guojie Song
3. Ning Zhang
4. Wei Lu
5. Wooram Heo
6. Qingye Jiang
7. Xinran He

In Statistical and Nonlinear Physics

1. Kyomin Jung
2. Wooram Heo
3. Guojie Song
4. Ning Zhang
5. Wei Lu
6. Qingye Jiang
7. Xinran He
8. Youze Tang

Citations in the corpus

• IRIE: Scalable and Robust Influence Maximization in Social Networks (2011, methodology): “Moreover, to show the wide applicability of our IRIE approach, we also adapt IRIE to the IC-N model, which considers negative opinions emerging and propagating in networks [2].”
• Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process (2012, background): “[1] extended the IC model to capture the propagation of negative opinions in information diffusion.”
• Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model (2011, methodology): “Finally the work of [4] studies negative opinions emerging from poor product or service qualities, not generated by competitors.”