In economics, it is well accepted that adoption of items is governed by the utility that a user derives from their adoption. In this paper, we propose a model called EPIC that combines utility-driven item adoption with the viral network effect helping to propagate adoption of and desire for items from users to their peers. We focus on the case of mutually complementary items and model their adoption behavior via supermodular value functions. We assume price is additive and use zero mean random noise to capture the uncertainty in our knowledge of user valuations. In this setting, we study a novel problem ofsocial welfare maximization : given item budgets, find an optimal allocation of items to seed nodes that maximizes the sum of expected utilities derived by users when the diffusion terminates . We show the expected social welfare is monotone but neither submodular nor supermodular . Nevertheless, we show that a simple greedy allocation can ensure a (1-1/e-\epsilon) -approximation to the optimum . To the best of our knowledge, this is the first instance where for a non-submodular objective in the context of viral marketing, such a high approximation ratio is achieved. We provide the analysis of this result, which is highly nontrivial and along the way we give a solution to the prefix-preserving influence maximization problem, which could be of independent interest. With extensive\textsf{  experiments on real and synthetic datasets, we show that our algorithm significantly outperforms all the baselines.
Motivated by applications such as viral marketing, the problem of influence maximization (IM) has been extensively studied in the literature. The goal is to select a small number of users to adopt an item such that it results in a large cascade of adoptions by others. Existing works have three key limitations. (1) They do not account for economic considerations of a user in buying/adopting items. (2) Most studies on multiple items focus on competition, with complementary items receiving limited attention. (3) For the network owner, maximizing social welfare is important to ensure customer loyalty, which is not addressed in prior work in the IM literature. In this paper, we address all three limitations and propose a novel model called UIC that combines utility-driven item adoption with influence propagation over networks. Focusing on the mutually complementary setting, we formulate the problem of social welfare maximization in this novel setting . We show that while the objective function is neither submodular nor supermodular , surprisingly a simple greedy allocation algorithm achieves a factor of (1-1/e-\epsilon) of the optimum expected social welfare. We develop\textsf{bundleGRD , a scalable version of this approximation algorithm, and demonstrate, with comprehensive experiments on real and synthetic datasets, that it significantly outperforms all baselines.
R
In economics, it is well accepted that adoption of items is governed by the utility that a user derives from their adoption.
Motivated by applications such as viral marketing, the problem of influence maximization (IM) has been extensively studied in the literature. The goal is to select a small number of users to adopt an item such that it results in a large cascade of adoptions by others. Existing works have three key limitations. (1) They do not account for economic considerations of a user in buying/adopting items. (2) Most studies on multiple items focus on competition, with complementary items receiving limited attention. (3) For the network owner, maximizing social welfare is important to ensure customer loyalty, which is not addressed in prior work in the IM literature.
R
propose a model called EPIC
address all three limitations and propose a novel model called UIC
R
the viral network effect helping to propagate adoption of and desire for items from users to their peers. We focus on the case of mutually complementary items and model their adoption behavior via supermodular value functions. We assume price is additive and use zero mean random noise to capture the uncertainty in our knowledge of user valuations. In this
influence propagation over networks. Focusing on the mutually complementary
D
study a novel problem of
D
social welfare maximization
R
: given item budgets, find an optimal allocation of items to seed nodes that maximizes the sum of expected utilities derived by users when the diffusion terminates
formulate the problem of social welfare maximization in this novel setting
R
the expected social welfare is monotone but
that while the objective function is
R
. Nevertheless, we show that
, surprisingly
R
can ensure a
algorithm achieves a factor of
R
-approximation to the optimum . To the best of our knowledge, this is the first instance where for a non-submodular objective in the context of viral marketing, such a high approximation ratio is achieved. We provide the analysis of this result, which is highly nontrivial and along the way we give a solution to the prefix-preserving influence maximization problem, which could be of independent interest. With extensive
of the optimum expected social welfare. We develop
A
bundleGRD
A
, a scalable version of this approximation algorithm, and demonstrate, with comprehensive
R
we show that our algorithm
that it
D
the