Browsing by Author "Raghavan, S."

Now showing 1 - 3 of 3

Metadata only
A branch‐and‐cut approach for the least cost influence problem on social networks
(Wiley, 2020-07) Danış, Dilek Günneç; Raghavan, S.; Zhang, R.; Industrial Engineering; DANIŞ, Dilek Günneç
This paper studies a problem in the online targeted marketing setting called the least cost influence problem (LCIP) that is known to be NP-hard. The goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentives) required to influence a given population. We develop a branch-and-cut approach to solve this LCIP on arbitrary graphs. We build upon Gunnec et al.'s novel totally unimodular (TU) formulation for the LCIP on trees. The key observation in applying this TU formulation to arbitrary graphs is to enforce an exponential set of inequalities that ensure the influence propagation network is acyclic. We also design several enhancements to the branch-and-cut procedure that improve its performance. We provide a large set of computational experiments on real-world graphs with up to 155 000 nodes and 327 000 edges that demonstrates the efficacy of the branch-and-cut approach. This branch-and-cut approach finds solutions that are on average 1.87% away from optimality based on a test-bed of 160 real-world graph instances. We also develop a heuristic that prioritizes nodes that receive low influence from their peers. This heuristic works particularly well on arbitrary graphs, providing solutions that are on average 1.99% away from optimality. Finally, we observe that partial incentives can result in significant cost savings, over 55% on average, compared to the setting where partial incentives are not allowed.
Metadata only
Integrating social network effects in the share-of-choice problem
(Wiley, 2017-12) Danış, Dilek Günneç; Raghavan, S.; Industrial Engineering; DANIŞ, Dilek Günneç
Accounting for social network effects in marketing strategies has become an important issue. Taking a step back, we seek to incorporate and analyze social network effects on new product development and then propose a model to engineer product diffusion over a social network. We build upon the share-of-choice (SOC) problem, which is a strategic combinatorial optimization problem used commonly as one of the methods to analyze conjoint analysis data by marketers in order to identify a product with largest market share, and show how to incorporate social network effects in the SOC problem. We construct a genetic algorithm to solve this computationally challenging (NP-Hard) problem and show that ignoring social network effects in the design phase results in a significantly lower market share for a product. In this setting, we introduce the secondary operational problem of determining the least expensive way of influencing individuals and strengthening product diffusion over a social network. This secondary problem is of independent interest, as it addresses contagion models and the issue of intervening in diffusion over a social network, which are of significant interest in marketing and epidemiological settings.
Metadata only
Least-cost influence maximization on social networks
(Informs, 2020-03) Danış, Dilek Günneç; Raghavan, S.; Zhang, R.; Industrial Engineering; DANIŞ, Dilek Günneç
Viral-marketing strategies are of significant interest in the online economy. Roughly, in these problems, one seeks to identify which individuals to strategically target in a social network so that a given proportion of the network is influenced at minimum cost. Earlier literature has focused primarily on problems where a fixed inducement is provided to those targeted. In contrast, resembling the practical viral-marketing setting, we consider this problem where one is allowed to "partially influence" (by the use of monetary inducements) those selected for targeting. We thus focus on the "least-cost influence problem (LCIP)": an influence-maximization problem where the goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentive) required to influence a given proportion of the population. Motivated by the desire to develop a better understanding of fundamental problems in social-network analytics, we seek to develop (exact) optimization approaches for the LCIP. Our paper makes several contributions, including (i) showing that the problem is NP-complete in general as well as under a wide variety of special conditions; (ii) providing an influence greedy algorithm to solve the problem polynomially on trees, where we require 100% adoption and all neighbors exert equal influence on a node; and (iii) a totally unimodular formulation for this tree case.