Paper Info
Title
Influence Maximization with Latency Requirements on Social Networks
Abstract
Targeted marketing strategies are of significant interest in the smartapp economy. Typically, one seeks to identify individuals to strategically target in a social network so that the network is influenced at a minimal cost. In many practical settings, the effects of direct influence predominate, leading to the positive influence dominating set with partial payments (PIDS-PP) problem that we discuss in this paper. The PIDS-PP problem is NP-complete because it generalizes the dominating set problem. We discuss several mixed integer programming formulations for the PIDS-PP problem. First, we describe two compact formulations on the payment space. We then develop a stronger compact extended formulation. We show that when the underlying graph is a tree, this compact extended formulation provides integral solutions for the node selection variables. In conjunction, we describe a polynomial-time dynamic programming algorithm for the PIDS-PP problem on trees. We project the compact extended formulation onto the payment space, providing an equivalently strong formulation that has exponentially many constraints. We present a polynomial time algorithm to solve the associated separation problem. Our computational experience on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) demonstrates the efficacy of our strongest payment space formulation. It finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality.
Year
DOI
Venue
2022
10.1287/ijoc.2021.1095
INFORMS JOURNAL ON COMPUTING
Keywords
DocType
Volume
social networks, influence maximization, latency constraints, mixed integer programming, strong models
Journal
34
Issue
ISSN
Citations 
2
1091-9856
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
S. Raghavan121616.30
Rui Zhang200.34