A Polyhedral Approach to Least Cost Influence Maximization in Social Networks

Intricate connections between entities in many natural and man-made systems form large complex networks. Of particular interest in network science is to gain insight into the dynamic of cascading processes in complex networks. For instance, the spreading of new behaviors, opinions, technologies, conventions, and gossips from person to person through a social network may play an important role in designing competitive marketing strategies. Indeed, the collection of social ties among consumers can be exploited to select pivotal early adopters for initiation and anticipate the time and cost required for the information propagation. Therefore, a key research question has been focused on how to efficiently identify a set of users to disseminate a certain information within the network, result in an increasing trend in studying social influence and information propagation in social networks (see, e.g., [1, 2]). As it may be expected, the spreading of social influence is commonly studied on network graphs that consist of nodes and links representing users and their connections, as well as a framework that describes how the information propagates among various intermediate users over time. Granovetter [3] first presented the threshold model to simulate the collective force exerted by a group on each of its members for predicting innovation and rumor diffusion, voting trends, and migration. A distinct threshold value is assigned to each user representing the proportion of neighbors who make a decision before a particular user makes such decision. Many extensions built on the threshold model have been proposed to encompass different circumstances. Among them, the linear threshold model and independent cascade model are the two most popular and well-studied one. Kempe et al. [4] study the linear threshold and independent cascade models under the influence maximization (IM) problem. The goal of IM is to activate as many nodes as possible by the end of propagation process given selected influential nodes within budget. Specifically, they show that the expected influence spread is a monotone submodular function, which can be approximated by greedy algorithm with performance guarantee $1-\frac{1}{e}-\epsilon$. On the other hand, the target set selection (TSS) introduced by [5] aims to find the minimum number of users required initially and activate the entire network through the propagation process. These two types of problems are fundamental in social network analysis and have many variants. Here we refer the reader to a survey of hardness and solution approaches for TSS [6], a review on approximation algorithms for IM [7], and a comprehensive review on introduction to types of social networks, properties, evaluation metrics and known method to solve IM [8]. Recently, Azaouzi et al. [9] presented a comprehensive review on models and methods of group-level IM and IM under privacy protection.

In this paper, we study an optimization problem arising in social network analytics, referred to as the least cost influence maximization (LCIM) problem [10, 11, 12]. The propagation process in LCIM is based on the linear threshold model, where each user is assigned a real-valued threshold and each link between users is assigned a weight to represent influence level. If the summation of influence weights from neighbors exceeds one’s threshold value, then the individual is activated, meaning that the information is adopted or the person changes their opinion to align with friends (neighbor nodes) in the social network. In LCIM, the concept of influence weights is extended with the idea of giving partial incentives such as free samples or coupons to individual as a motivation for spreading information. The assumption of the linear threshold model allows the incentives and influence weights in the activation processes to be linearly additive, which immediately admits a mixed-integer optimization formulation for the influence propagation. Our goal is to develop an exact computational method based on the polyhedral structure. We assume that all the parameters are deterministic, all the nodes are inactive initially and nodes remain activated once the influence weights exceeds the threshold. A similar assumption on using deterministic parameters in linear threshold model can be found in [13]. From a practical point of view, the assumption of deterministic linear threshold depends on the accuracy of estimation of influence factors and threshold parameters. Machine learning and data mining techniques may enable one to obtain accurate predictions on those parameters from massive amounts of data available nowadays. Note that when incentive is allowed and the influence weights and thresholds are considered known in the problem, the influence propagation is no longer submodular, thus, a greedy algorithm is not applicable for arbitrary graphs. However, the problem is still challenging to solve due to the combinatorial nature. The minimum subset of nodes required under dynamic activation is also referred to as the dynamic monopoly, where nodes become activated if at least half of the neighbors are activated in the previous time period. Hence, an extra index of time is incorporated into the integer programming formulation to describe step-by-step activation of nodes, see [14, 15, 16]. We do not consider time dynamics in our problem despite the fact that the influence propagation occurs in discrete steps. Moreover, the induced optimal influence propagation graph for LCIM in the static network setting given by the mixed-integer programming formulation is known to be acyclic [10].

Even though IM, TSS and LCIM problems share certain similarities, most of the previous studies on IM or TSS mainly focus on developing degree-based or centrality-based metaheuristics and approximation algorithms. Existing studies on using exact mixed-integer optimization techniques for LCIM under deterministic data settings are relatively limited. The computational complexity of LCIM is established in [12]. In particular, they show that LCIM is NP-hard on arbitrary graphs and bipartite graphs for both equal and unequal influence when 100% penetration rate is not required. They also give a greedy algorithm and a total unimodular formulation for LCIM with equal influence on a tree and 100% penetration rate. Günneç et al. [11] develop a branch-and-cut algorithm using this total unimodular formulation for LCIM on arbitrary graphs. Fischetti et al. [10] present a novel set covering formulation for a generalized LCIM, where the activation function can be adjusted to be nonlinear in order to capture the situation of diminishing marginal influences or over-proportional effect from peers. They propose strengthened generalized propagation inequalities and a price-cut-and-branch algorithm to deal with the exponential number of variables and constraints. Recent developments on using exact mixed-integer optimization methods for stochastic influence maximization problem include a delayed constraint generation algorithm for a two-stage stochastic influence maximization problem [17] and a branch-cut-and-price algorithms for robust a influence maximization, where node thresholds and arc influence factors are subject to budget uncertainty [18].

To develop a strong formulation for LCIM, we study the polyhedral structure of constraints (1a). For $i\in V$, let

The set $\mathcal{P}_{i}$ is a mixing set with a binary variable on the right-hand side value. For any inequality that is facet-defining for $\operatorname{conv}{(\mathcal{P}_{i})}$, it is facet-defining for $\operatorname{conv}{(\cap_{i\in V}\mathcal{P}_{i})}$ as well. Therefore, we now consider a single node propagation by dropping the subscript $i$ and obtain the following set

Observe that the set $\mathcal{P}$ contains a mixed 0-1 knapsack structure. Let set $\mathcal{\overline{P}}$ obtained from $\mathcal{P}$ by setting $\overline{y}_{j}=1-y_{j}$, $j\in N$ and $z=1$, then we have a mixed 0-1 knapsack set $\overline{\mathcal{P}}$ with weight $d_{j}$ for each item $j\in N$ and the capacity of knapsack $\sum_{j\in N}d_{j}-h$ plus an unbounded continuous variable $x$ in the following

The mixed 0-1 knapsack set $\overline{\mathcal{P}}$ is a special case of traditional 0-1 knapsack problem where the knapsack size is expanded with additional capacity. Observe that $\dim(\mathcal{P})$ is full-dimensional and contains the origin. There are trivial facets for $\operatorname{conv}{(\mathcal{P})}$ and their verification is straightforward.

The first result of Proposition 1 validates our data pre-processing assumption for influence weight and threshold when $d_{ij}>h_{i}$. To show this, consider a single node influence propagation inequality

Clearly, this inequality is dominated by

as the second inequality is faced-defining. Hence, we can obtain the facet-defining inequality by simply substituting any influence weight $d_{ji}$ with $h_{i}$ for all $j\in N(i)$ if $d_{ji}>h_{i}$. Marchand and Wolsey [21] propose two classes of valid inequalities for $\overline{\mathcal{P}}$ based on mixed-integer rounding and lifting function, namely, the continuous cover and continuous packing (reversed cover) inequalities. We follow a similar idea to strengthen the formulation for LCIM with moderate modification as $\overline{\mathcal{P}}\subset\mathcal{P}$. Applications of continuous cover and continuous packing inequalities for $\mathcal{\overline{P}}$ can be seen in several fields, including delay management for public transportation [22], job scheduling with uncertain multiple resources [23], discrete lot sizing [24] and single-item capacitated lot sizing [25]. They can also be extended to solve general mixed-integer optimization that contains mixed 0-1 knapsack set with bounded continuous variables, see [26, 27, 28].

In this section, we expand the study of $\operatorname{conv}{(\cap_{i\in V}\mathcal{P}_{i})}$ to incorporate the remaining constraints in LCIM on an arbitrary bidirectional graph that contains cycles. The polyhedron that describes the intersection of these constraints is

To simplify the notation, we let $\boldsymbol{\alpha}$ and $\boldsymbol{\beta}$ be the coefficients associated with variables $\mathbf{y}$ and $\mathbf{z}$ corresponding to continuous cover and continuous packing inequalities. In other words, we express them in the following form:

and it is facet-defining for $\operatorname{conv}{(\mathcal{Q})}$. Due to the straightforward structure of a cycle, the minimum incentive of the influence propagation can be easily characterized. Raghavan and Zhang [29] give an $O(n)$ time algorithm for the weighted target set selection problem on a cycle. We also present a polynomial time dynamic programming to solve LCIM on a simple cycle. Then we give a class of exponential number of valid inequalities that forms acyclic influence propagation by exploiting inequality (8) as the base inequality. We also demonstrate that the separation for this class of valid inequalities can be done in polynomial time for arbitrary bidirectional graphs that contain cycles.