Threshold Models for Competitive Influence in Social Networks

Lecture notes in computer sciencePublished 1 January 2010

Allan Borodin, Yuval Filmus, Joel Oren

DOI10.1007/978-3-642-17572-5_48

Source URL

Citations316

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

It is shown that for a broad family of competitive influence models, it is NP-hard to achieve an approximation that is better than a square root of the optimal solution.

Abstract

The problem of influence maximization deals with choosing the optimal set of nodes in a social network so as to maximize the resulting spread of a technology (opinion, product-ownership, etc.), given a model of diffusion of influence in a network. A natural extension is a competitive setting, in which the goal is to maximize the spread of our technology in the presence of one or more competitors. We suggest several natural extensions to the well-studied linear threshold model, showing that the original greedy approach cannot be used. Furthermore, we show that for a broad family of competitive influence models, it is NP-hard to achieve an approximation that is better than a square root of the optimal solution; the same proof can also be applied to give a negative result for a conjecture in [2] about a general cascade model for competitive diffusion. Finally, we suggest a natural model that is amenable to the greedy approach.

Keywords

Decision SciencesPhysics and Astronomy

Maximizing the spread of influence through a social network

7,314 Citations2003David Kempe, Jon Kleinberg +1 more

An analysis framework based on submodular functions shows that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models, and suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.

Mathematical ProgrammingAn analysis of approximations for maximizing submodular set functions—I

4,458 Citations1978George L. Nemhauser, Laurence A. Wolsey +1 more

It is shown that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1/K]K times the optimal value, which can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.

Mining the network value of customers

2,868 Citations2001Pedro Domingos, Matt Richardson

It is proposed to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively, taking advantage of the availability of large relevant databases.

Journal of Consumer ResearchSocial Ties and Word-of-Mouth Referral Behavior

2,366 Citations1987Jacqueline Johnson Brown, Peter H. Reingen

Lecture notes in computer scienceCompetitive Influence Maximization in Social Networks

511 Citations2007S. Bharathi, David Kempe +1 more

A natural and mathematically tractable model for the diffusion of multiple innovations in a network, and a (1-1/e) approximation algorithm for computing the best response to an opponent's strategy are given.

Lecture notes in computer scienceInternet and Network Economics

316 Citations2005Xiaotie Deng, Yinyu Ye

Maximizing influence in a competitive social network

250 Citations2007Tim Carnes, Chandrashekhar Nagarajan +2 more

This work considers the problem faced by a company that wants to use viral marketing to introduce a new product into a market where a competing product is already being introduced and proposes two models for the spread of influence of competing technologies through a social network.

Lecture notes in computer scienceWord of Mouth: Rumor Dissemination in Social Networks

203 Citations2008Jan Kostka, Yvonne Anne Oswald +1 more

This paper uses concepts of game theory and location theory and model the selection of starting nodes for the rumors as a strategic game and proves that computing the optimal strategy for both the first and the second player is NP-complete, even in a most restricted model.

Lecture notes in computer scienceThe Cover Times of Random Walks on Hypergraphs

137 Citations2011Colin Cooper, Alan Frieze +1 more

An expression for C(H) is given which is tractable for many classes of hypergraphs, and C (H) and I(H ) are calculated exactly for random r-regular, s-uniform hyper graphs.

View PDF

SIAM Journal on ComputingSubmodularity of Influence in Social Networks: From Local to Global

97 Citations2010Elchanan Mossel, Sébastien Roch

The results demonstrate that “local” submodularity is preserved “globally” under this diffusion process, which is of natural computational interest, as many optimization problems have good approximation algorithms for submodular functions.