Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization

In the past few years, with the exponential growth in trajectory databases [37, 44], the study of trajectory-based influence maximization has increased in both online and out-of-home advertisements [2, 39, 44, 41, 33, 30]. Most influence maximization studies are conducted in the context of social network advertisements [33, 30, 13, 14]. There are a few in the context of billboard advertisements [2, 6, 41]. However, there is no literature that considers both social networks and billboard advertising jointly to maximize an advertiser’s influence and to utilize the advertiser’s budget. Several works relate closely to our budget split problem. In particular, billboard advertisements, Zhang et al.[41] studied trajectory-driven billboard placement using a greedy algorithm with a $(1-1/e)$ approximation. Later, Wang et al.[35] focused on targeted billboard selection using user mobility and ad relevance. Additionally, Zhang et al. [42] proposed a tangent-line-based method for billboard selection, achieving an approximation of $\frac{\theta }{2}(1-1/e)$. One relevant problem in social media advertising is selecting a limited number of highly influential users as seed users to maximize the influence. This problem has been referred to as the Social Influence Maximization Problem, and a plethora of solution methodologies are available in the literature [27, 14]. Later, Nugayan et al. [28] studied the influence maximization problem, assuming that each user in the network has a selection cost and that seeds must be selected within the allocated budget. The major difference between our work and previous studies is that previous studies allocate the advertiser’s budget entirely to either billboard or social network advertising. But in our work, we split the advertiser’s budget between two media (billboards and social networks) to maximize the advertiser’s total influence while ensuring the budget is used effectively.

In the Social Viral Marketing (SVM) setting, the influence provider platform, such as Twitter or Facebook, promotes advertisements on a social network. In return, the influence provider receives payments from advertisers. The common business model used is cost per engagement (CPE). Under this model, an advertiser pays the host for every click or engagement received by its advertisement [20, 24, 34]. Several recent studies have focused on SVM. One important line of work aims to minimize the regret of the influence provider [10, 11, 13]. In this setting, each advertiser specifies a required amount of influence. If the achieved influence is less than the demand, the advertiser pays only for the actual influence obtained. If the achieved influence exceeds the demand, the advertiser does not pay for the extra influence. As a result, both insufficient influence and excessive influence lead to regret for the influence provider [12, 5, 6, 4]. Other studies focus on maximizing revenue under the CPE model. In these works, the revenue is defined as the total payment collected from all advertisers. Each advertiser’s payment equals the sum of CPE values of the activated users [10, 13]. In the existing literature, two types of regret-minimization problems are studied in the context of advertising: SVM and Minimizing Regret for the OOH Advertising Market problem (MROAM). There are two major differences between the SVM and the MROAM problem. First, the business models are different. In SVM, the influence provider always receives payment based on engagements. In some cases, the influence provider may receive no payment at all if the advertiser’s demand is not met [43, 4]. Second, the influence models are different. In MROAM, influence is determined by geographical proximity. A billboard influences users who are physically close enough to encounter it. The influence does not spread from one user to another [2, 43, 4, 6]. In contrast, SVM uses probabilistic diffusion models, such as the Independent Cascade and Linear Threshold models. Under these models, influence propagates through the social network from one user to another [15, 16, 23]. Due to this difference, SVM research mainly focuses on estimating the spread of influence in virtual social networks. In contrast, MROAM relies on spatial interactions between users and billboards. Therefore, the optimization problems in these two settings are fundamentally different.

In a billboard advertisement, the key components are the trajectory and the billboard database. A trajectory database $𝔻$ contains location information of persons moving over time and is defined as a collection of tuples of the form $(u_i,loc,[t_1,t_2])$. This signifies that the person $u_i$ is at the location, $loc$ in between the time slot $[t_1,t_2]$. Let, $m$ number of tuples are in $𝔻$ and it contains the location information for the duration $[T_1,T_2]$ for $n$ persons $𝒰=\{u_1,u_2,\mathrm{\dots },u_n\}$. So, we can say every tuple $t\in 𝔻$, have the time stamp $[t_i,t_j]\subseteq [T_1,T_2]$. The billboard database $𝔹$ stores information on billboards placed across a city, represented as tuples $(b_{id},\text{loc},\text{time\_slot},\text{cost})$, where $b_{id}$ is the unique billboard ID, loc denotes its location, and cost is the rental price for that slot. Let $𝔹$ contain slot information for $r$ distinct billboards $ℬ=\{b_1,b_2,\mathrm{\dots },b_r\}$. A user $u_i\in 𝒰$ is said to be influenced by a billboard $b_j$ if their presence interval $[t_a,t_b]$ at the location overlaps with the ad display time $[t_x,t_y]$, i.e., $[t_a,t_b]\cap [t_x,t_y]\ne \mathrm{\varnothing }$, with some influence probability. Consider that an advertiser can lease a billboard for the duration $\mathrm{\Delta }$. Hence, for every billboard, the number of slots is $\frac{T_2-T_1}{\mathrm{\Delta }}$. As an example, the slot $(b_i,[t,t+\mathrm{\Delta }])$ signifies the slot from the duration from $t$ to $t+\mathrm{\Delta }$ for the billboard $b_i$. The set of all billboard slots is denoted by $ℬ𝒮$ and defined as $ℬ𝒮=\{(b_i,[t,t+\mathrm{\Delta }]):b_i\in 𝔹\text{ and }t\in \{T_1,T_1+\mathrm{\Delta },T_1+2\mathrm{\Delta },\mathrm{\dots },T_2-\mathrm{\Delta }\}\}$. Every billboard slot is associated with a cost, which is formalized by the cost function ${𝒞}_{ℬ}:ℬ𝒮⟶{ℝ}^{+}$. Now, given $𝕊\subseteq ℬ𝒮$, we denote the influence of slot set $𝕊$ by $ℐ(𝕊)$ and define it in Definition 2.

We adopt a widely used influence probability model [41, 43, 2, 6, 7], where the probability of a billboard slot $b{s}_i$ influencing a user $u_j$ is defined as $Pr(b{s}_i,u_j)=\frac{\text{Size}(b{s}_i)}{\underset{b{s}_i\in ℬ}{\max }\text{Size}(b{s}_i)}$, where $\text{Size}(b{s}_i)$ denotes the panel size of the billboard slot $b{s}_i$. The influence function $ℐ(\cdot )$ maps each subset of billboard slots to a non-negative real value, i.e., $ℐ:2^{ℬ𝒮}\to {ℝ}_0^{+}$, with $ℐ(\mathrm{\varnothing })=0$.

Consider, we know the social network of users $𝒰=\{u_1,u_2,\mathrm{\dots },u_n\}$, which is represented by a simple, weighted, and directed graph $𝒢(𝒰,ℰ,𝒫)$. The edge set $ℰ(𝒢)$ contains the binary social relationship (e.g., friendship, follower ship, etc.), and the edge weight function $𝒫$ that maps each edge to its corresponding influence probability, i.e., $𝒫:ℰ(𝒢)⟶(0,1]$. For each edge $(u_i{u}_j)$, its influence probability is denoted by ${𝒫}_{(u_i{u}_j)}$. If $(u_i{u}_j)\notin ℰ(𝒢)$, ${𝒫}_{(u_i{u}_j)}=0$. A key phenomenon in social networks is the diffusion of information. To study this, various diffusion models have been proposed, among which the Independent Cascade Model is one of the most widely used. The diffusion of influence begins with a seed set and propagates through the network. The influence of a seed set is measured by the total number of activated nodes at the end of the process. Formally, this is captured by the influence function $I_{𝒢}:2^{𝒰}\to {ℝ}_0^{+}$, where $I_{𝒢}(\mathrm{\varnothing })=0$. Under the IC Model, $I_{𝒢}$ is non-negative, monotone, and submodular [33].

Considering digital billboards and social networks, we aim to maximize their joint impact. To measure this, we introduce a combined influence model in Definition 4.

The influence function $\mathrm{\Phi }(.,.)$ is a mapping from all possible combinations of subsets of slots and seed sets to the influence, i.e., $\mathrm{\Phi }:2^{𝔹𝕊}\times 2^{𝒢}⟶{ℝ}_0^{+}$ with $\mathrm{\Phi }(\mathrm{\varnothing },\mathrm{\varnothing })=0$. The existing literature [29, 32, 18] considered the effect of interaction in advertising campaigns. However, there is no specific mechanism to compute it. We explicitly model this interaction effect and define it in Definition 5.

We study the problem of splitting a fixed budget B into $B_1$ for billboard and $B_2$ for social network advertising to maximize influence. We refer to this as the Budget Split Problem in Billboard and Social Network Advertisement, formally represented as $I(𝒢,𝕊,𝔻,𝔹,B)$ and defined in Definition 7.

From the computational point of view, this problem can be posed as follows.

The influence maximization problem in billboard [3] and social network [33] advertisement had an inapproximability result stated in Theorem 8. Therefore, the same inapproximability results also hold for our problem.

Algorithm 1 presents a greedy approach to solving the non-bisubmodular maximization problem. It takes billboard slot, trajectory, and social network as input and returns an allocation of slots and seed nodes under the given budget. It starts with empty sets for billboard slots and seeds. First, billboard slots are sorted by their individual influence. Slots are greedily added until the temporary budget is exhausted. Similarly, seed nodes are sorted by individual influence. Seeds are added until another temporary budget is used. The smaller size of these two sets is used to guide sampling. In each iteration, a small random subset of billboard slots is sampled. A small random subset of seed nodes is also sampled. For each sampled element, the marginal gain per unit cost is computed. The interaction effect is included in this computation. The element with the higher gain-to-cost ratio is selected. The budget is updated after every selection. The selected element is removed from further consideration. This process continues until the budget is exhausted.

Algorithm 2 selects billboard slots and social network seeds jointly. It works under a fixed budget. The algorithm runs in two phases. In the first phase, one billboard slot is selected first. It has the highest influence per unit cost. One social network seed is also selected. It has the highest influence per unit cost. If both fit the budget, both are chosen. Otherwise, only the better one is selected. This phase activates the interaction effect early. In the second phase, all remaining candidates are inserted into a priority queue. Each candidate is keyed by an upper bound on marginal gain per cost. At each iteration, the top candidate is examined. Its true marginal gain is computed lazily. If the gain matches the upper bound, it is selected. If not, the bound is updated and reinserted. Billboard slots and seed nodes are treated uniformly. Only budget-feasible candidates are added. The process continues until the budget is exhausted or no candidates remain.

For experimental evaluation, we used three datasets: Trajectory, Social Network, and Billboard. The trajectory and social network datasets used in our study have also been used by existing studies [39, 40]. All the datasets are summarized in Table 4. Next, since outdoor advertising companies such as LAMAR and JCDecaux do not disclose actual billboard rental prices, prior work assumes that slot cost is proportional to influence. Following this convention, we set the cost of a billboard slot $bs$ as $\lfloor \delta \cdot \frac{ℐ(bs)}{10}\rfloor$, where $\delta \in [0.8,1.1]$ is a scaling factor. Next, we evaluate three influence probability models: Uniform, Weighted Cascade, and Trivalency. In the uniform model, all edges have probability $p_c=0.1$; in the weighted cascade model, an edge $(u_i,u_j)$ has probability $1/\mathrm{deg}(u_i)$; and in the trivalency model, edge probabilities are sampled uniformly from $\{0.1,0.01,0.001\}$. For user selection cost, we adopt the degree-proportional cost model [30], where the cost of selecting a user $u$ is $𝒞(u)=k\cdot (|𝒱|/{\sum }_{v\in 𝒱}\mathrm{deg}(v))\cdot \mathrm{deg}(u)$. We set $k=1000$. All experiments were run on an HP Z4 workstation with an Xeon 3.50 GHz CPU and 64 GB RAM.

In Random Allocation (RA) approach, billboard slots and social media seeds are selected randomly. It randomly selects nodes without considering any influence maximization criterion and stops when the budget is exhausted. In Top-$k$ Allocation, most influential billboard slots and seed nodes are selected till their respective demand and budget constraints are satisfied. In High-Degree Heuristic (HDH) approach, billboard slots are sorted based on high impression count, and social media seeds are sorted by highest out-degree. It greedily selects nodes until the budget is exhausted. The Page Rank Based Selection (PRS/PGRS) selects influential nodes based on their global importance by computing PageRank scores and choosing the top-ranked nodes until the budget is exhausted.

The following research questions are our focus in this study.RQ1: Varying budgets, how the influence of social networks and billboards varies. RQ2: Varying budgets, how the budget split ratio in social networks and billboard advertisements varies. RQ3: Varying budgets, how the overall influence and run time vary.