Multistage Campaigning in Social Networks

Introduction

Obama was the first US president in history who successfully leveraged online social media in presidential campaigning, which has been popularized and become a ubiquitous approach to electoral politics (such as in the on-going 2016 US presidential election) in contrast to the decreasing relevance of traditional media such as TV and newspapers . The power of campaigning via social media in modern politics is a consequence of online social networking being an important part of people’s regular daily social lives. It has been quite common that individuals use social network sites to share their ideas and comment on other people’s opinions. In recent years, large organizations, such as governments, public media, and business corporations, also start to announce news, spread ideas, and/or post advertisements in order to steer the public opinion through social media platform. There has been extensive interest for these entities to influence the public’s view and manipulate the trend by incentivizing influential users to endorse their ideas/merits/opinions at certain monetary expenses or credits. To obtain most cost-effective trend manipulations, one needs to design an optimal campaigning strategy or policy such that quantities of interests, such as influence of opinions, exposure of a campaign, adoption of new products, can be maximized or steered towards the target amount given realistic budget constraints.

The key factor differentiating social networks from traditional media is peer influence. In fact, events in an online social network can be categorized roughly into two types: endogenous events where users just respond to the actions of their neighbors within the network, and exogenous events where users take actions due to drives external to the network. Then it is natural to raise the following fundamental questions regarding optimal campaigning over social networks: can we model and exploit those event data to steer the online community to a desired exposure level? More specifically, can we drive the overall exposure to a campaign to a certain level (e.g., at least twice per week per user) by incentivizing a small number of users to take more initiatives? What about maximizing the overall exposure for a target group of people?

More importantly, those exposure shaping tasks are more effective when the interventions are implemented in multiple stages. Due to the inherent uncertainty in social behavior, the outcome of each intervention may not be fully predictable but can be anticipated to some extent before the next intervention happens. A key aspect of such situations is that interventions can’t be viewed in isolation since one must balance the desire for high present reward with the penalty of low future outcome.

In this paper, the dynamic programming framework is employed to tackle the aforementioned issues. In particular, we first establish the fundamental theory of optimal campaigning over social networks where the user activities are modeled as a multivariate Hawkes process (MHP) since MHP can capture both endogenous and exogenous event intensities. We also derive a time dependent linear relation between the intensity of exogenous events and the overall exposure to the campaign. Exploiting this connection, we develop a convex dynamic programming framework for determining the optimal intervention policy that prescribes the required level of external drive at each stage in order for the campaign to reach a desired exposure profile. We propose several objective functions that are commonly considered as campaigning criteria in social networks. Experiments on both synthetic data and real world network of news websites in the MemeTracker dataset show that our algorithms can shape the exposure of campaigns much more accurately than baselines.

Illustrative Example

Next sections will define the campaigning problem formally. However, we found it beneficial to formulate it more intuitively. Next section will define all the concepts appeared here rigorously.

Fig. 1-a shows a hypothetical social network highlighting 4 users and their influence on each other. They have their own set of followers which for simplicity are considered disjoint and being influenced equally. Our objective in this toy example is to maximize the minimum exposure on the followers. For the ease of exposition, we only consider 2 stages which in the beginning we can intervene. Hypothetically, we are going to advertise iPhone 7 on behalf of Apple Inc.

Now, we intuitively proceed to find the optimum intervention. At the first stage, where the state is zero (no exposure from the past), intervention through Jacob and Christine would not be part of the solution (or their share would be negligible), because the outcome would be small due to the low number of total followers and the small amount of influence. Between Bob and Sophie, we would select her. Note that Sophie has a high influence on Bob and if she is incentivized to make a blog post for the campaign, she can make Bob interested too. Therefore, the procedure will assign most budget to Sophie. Furthermore, Bob has a high influence on Jacob and will probably inspire him to do an activity. Let’s follow a hypothetical scenario. Sophie makes her post at 9:35am about apple’s new phone. Bob is notified about her post and will make an inspiring post about the phone’s camera. However, Jacob will not respond to this campaign well, e.g., he may be traveling that day. This phenomenon is perfectly captured via the probabilistic framework for event analysis . On the other hand, Christine who is not a big fan of Bob’s post compared to Jacob will respond to Bob’s post by writing a comparison between Apple and Samsung’s product at 3:47pm. This will reinforce Bob to make a separate post explaining the features of Apple’s new product. These events are illustrated in Fig. 1-b.

The cascade of events at the first stage will expose followers of Sophia, Bob, and Christine to the new product. However, all things do not go according to our expectation. Jacob happens to be out of his office that day and his followers are not aware of the news. Considering the MEM as the objective function, this is quite disappointing that there are people who are exposed to the campaign 0 times. Exposures of followers are demonstrated in Fig. 1-b. This is the point where multi-stage dynamic campaigning helps. Considering the exposure intensity of followers in Fig. 1-c, Christine’s, Bob’s, and even Sophia’s followers are still under the influence. Furthermore, they may follow their initial posts by new ones. Then, in the next stage, it looks reasonable to invest on Jacob. At least his followers will notify about the campaign and also as Jacob has an influence on Sophie, his posts may inspire Sophie again and this may increase the exposure intensity of followers of Sophie as well. Therefore, thanks to a second chance in intervention, Jacob will get the most budget at the second stage to advertise the product.

Basics and Background

and hence $\mathcal{N}^{i}(t)=\int_{0}^{t}d\mathcal{N}^{i}(s)$, where $\delta(t)$ is a Dirac delta function. The point process representation of temporal data is fundamentally different from the discrete time representation typically used in social network analysis. It directly models the time interval between events as random variables, avoids the need to pick a time window to aggregate events, and allows temporal events to be modeled in a fine grained fashion. Moreover, it has a remarkably rich theoretical support .

An important way to characterize temporal point processes is via the conditional intensity function — a stochastic model for the time of the next event given all the times of previous events. Formally, the conditional intensity function $\lambda^{i}(t)$ (intensity, for short) of user $i$ is the conditional probability of observing an event in a small window $[t,t+dt)$ given the history $\mathcal{H}(t)=\left\{\mathcal{H}^{1}(t),\ldots,\mathcal{H}^{n}(t)\right\}$:

where one typically assumes that only one event can happen in a small window of size $dt$. Fig. 1-b and Fig. 1-c show the events and intensity function of the activities of the 4 users in the social network respectively. Furthermore, these two can be seen as the exposure events and the exposure intensity function to their followers since for simplicity we are just considering the activities of these 4 users in the network. The functional form of the intensity $\lambda^{i}(t)$ is often designed to capture the phenomena of interests.

The Hawkes process is a class of self and mutually exciting point process models,

where the intensity is history dependent. $\phi^{ij}(t,s)$ is the impact function capturing the temporal influence of an event by user $j$ at time $s$ to the future events of user $j$ at time $t\geqslant s$. Here, the first term $\mu^{i}(t)$ is the exogenous event intensity modeling drive outside the network and indecent of the history, and the second term $\sum_{k:t_{k}<t}\phi^{id_{k}}(t,t_{k})$ is the endogenous event intensity modeling interactions within the network . Defining $\Phi(t,s)=[\phi^{ij}(t,s)]_{i,j=1\ldots n}$, and $\lambda(t)=(\lambda^{1}(t),\ldots,\lambda^{n}(t))^{\top}$, and $\mu(t)=(\mu^{1}(t),\ldots,\mu^{n}(t))^{\top}$ we can compactly rewrite Eq 3 in matrix form:

In practice it is standard to employ shift-invariant impact function, i.e., $\Phi(t,s)=\Phi(t-s)$. Then, by using notation of convolution $f(t)*g(t)=\int_{0}^{t}f(t-s)g(s)ds$ we have

From Intensity to Average Activity

In particular, if $\Phi(t)=Ae^{-\omega t}\mathbf{1}_{\geq 0}(t)=[a_{ij}e^{-\omega t}\mathbf{1}_{\geq 0}(t)]_{ij}$ where $0\leq\omega\notin\text{Spectrum}(A)$, then

for $t\in[0,T]$, where, $\mathbf{1}_{\geq 0}(t)$ is an indicator function for $t\geq 0$.

where $0=\tau_{0}<\tau_{1}<\cdots<\tau_{M}=T$ is a finite partition of time interval $[0,T]$ and function $\mathbf{1}_{[\tau_{m-1},\tau_{m})}(t)$ indicates $\tau_{m-1}\leq t<\tau_{m}$. The next theorem shows that if $\Psi(t)$ satisfies (8), then one can calculate $\eta(t)$ for piecewise constant intensity $\mu:[0,T]$ of form (10).

Let $\Psi(t)$ satisfy (8) and $\mu(t)$ be a right-continuous piecewise constant intensity function of form (10), then the rate function $\eta(t)$ is given by

for all $t\in(\tau_{m-1},\tau_{m}]$ and $m=1,\dots,M$, where $c_{-1}:=0$ by convention.

Using the above lemma, for the first time, we derive the average intensity for a general exogenous intensity. Section 7 includes a few experiments to investigate these results empirically.

If $\Psi\in C^{1}([0,T])$ and satisfies (8), and exogenous intensity $\mu$ is bounded and piecewise absolutely continuous on $[0,T]$ where $\mu(t+)=\mu(t)$ at all discontinuous points $t$, then $\mu$ is differentiable almost everywhere, and the semi-indefinite integral

Suppose $\Psi$ and $\mu$ satisfy the same conditions as in Thm. 3, and define $\psi=\Psi^{\prime}$, then the rate function is $\eta(t)=(\psi*\mu)(t)$. In particular, if $\Phi(t)=Ae^{-\omega t}\mathbf{1}_{\geq 0}(t)=[a_{ij}e^{-\omega t}\mathbf{1}_{\geq 0}(t)]_{ij}$ then the rate function $\eta(t)=\mu(t)+A\int_{0}^{t}e^{(A-wI)(t-s)}\mu(s)ds$.

Multi-stage Closed-loop Control Problem

Given the analytical relation between exogenous intensity and expected overall intensity (rate function), one can solve a single one-stage campaigning problem to find the optimal constant intervention intensity . Alternatively, the time window can be partitioned into multiple stages and one can impose different levels of interventions in these stages. This yields an open-loop optimization of the cost function where one selects all the intervention actions at initial time 0. More effectively, we tackle the campaigning problem in a dynamic and adaptive manner where we can postpone deciding the intervention by observing the process until the next stage begins. This is called the closed-loop optimization of the objective function.

Event exposure is the quantity of major interests in campaigning. The exposure process is mathematically represented as a counting process, $\mathcal{E}(t)=(\mathcal{E}^{1}(t),\ldots,\mathcal{E}^{n}(t))^{\top}$: Here, $\mathcal{E}^{i}(t)$ records the number of times user $i$ is exposed (she or one of her neighbors performs an activity) to the campaign by time $t$. Let $B$ be the adjacency matrix of the user network, i.e., $b_{ij}=1$ if user $i$ follows user $j$ or equivalently user $j$ influences user $i$. We assume $b_{ii}=1$ for all $i$. Then the exposure process is given by $\mathcal{E}(t)=B\,\mathcal{N}(t).$

2 Stages and interventions

3 States and state evolution

Note that the Hawkes process is non-Markov and one needs complete knowledge of the history to characterize the entire process. However, the conditional intensity $\lambda(t)$ only depends on the state of process at time $t$ when the standard exponential kernel $\Phi(t,s)=Ae^{-\omega(t-s)}\mathbf{1}_{\geq 0}(t-s)$ is employed. In this case, the activity rate at stage $m$ is

Define $x_{m}:=\lambda_{m-1}(\tau_{m})-u_{m-1}-\mu$ (and $x_{0}=0$ by convention) then the intensity due to events of all previous $m$ stages can be written as $\int_{0}^{\tau_{m}}Ae^{-\omega(t-s)}\,d\mathcal{N}(s)=x_{m}e^{-\omega(t-\tau_{m})}$. In other words, $x_{m}$ is sufficient to encode the information of activity in the past $m$ stages that is relevant to future. This is in sharp contrast to the general case where the state space grows with the number of events.

4 Objective function

Capped Exposure Maximization (CEM): In real networks, there is a cap on the exposure each user can tolerate due to the limited attention of a user. Suppose we know the upper bound $\beta_{m}^{i}$ , on user $i$’s exposure tolerance over which the extra exposure is not counted towards the objective. Then, we can form the following capped exposure maximization

Minimum Exposure Maximization (MEM): Suppose our goal is instead to maintain the exposure of campaign on each user above a certain minimum level, at each stage or, alternatively to make the user with the minimum exposure as exposed as possible, we can consider the following cost function:

5 Policy and actions

To summarize, the following problem is formulated to find the optimal control policy $\pi$:

Closed-loop Dynamic Programming Solution

We have formulated the control problem as an optimization in (18). However, when control policy $\pi_{m}$ is to be implemented, only $x_{m}$ is observed and there are still uncertainties in future $\{x_{m+1},\dots,x_{M-1}\}$. For instance, when $\pi_{m}$ is implemented according to $x_{m}$ starting from time $\tau_{m}$, the intensity $x_{m+1}:=f(x_{m},\pi_{m}(x_{m}))$ at time $\tau_{m+1}$ depends on $x_{m}$ and the control $\pi_{m}(x_{m})$, but is also random due to the stochasticity of the process during time $[\tau_{m},\tau_{m+1})$. Therefore, the design of $\pi$ needs to take future uncertainties into considerations.

Suppose we have arrived at stage $M$ at time $\tau_{M-1}$ with observation $x_{M-1}$, then the optimal policy $\pi_{M-1}$ satisfies $g_{M-1}(x_{M-1},\pi_{M-1}(x_{M-1}))=\max_{u\in\mathcal{U}_{M-1}}g_{M-1}(x_{M-1},u)=:J_{M-1}(x_{M-1})$. We then repeat this procedure for $m$ from $M-1$ to backward to find the sequence of controls via dynamic programming such that the control $\pi_{m}(x_{m})\in\mathcal{U}_{m}$ yields optimal objective value

Solving $\eqref{eq:dynamic-programming}$ for finding $J_{m}(x_{m})$ analytically is intractable. Therefore, we will adopt an approximate dynamic programming scheme. In fact approximate control is as essential part of dynamic programming as the optimization is usually intractable due to curse of dimensionality except a few especial cases . Here we adopt a suboptimal control scheme, certainty equivalent control (CEC), which applies at each stage the control that would be optimal if the uncertain quantities were fixed at some typical values like the average behavior. It results in an optimal control sequence, the first component of which is used at the current stage, while the remaining components are discarded. The procedure is repeated for the remaining stages. Algorithm 1 summarizes the dynamic programing steps. This algorithm has two parts: (i) certainty equivalence which the random behavior is replaced by its average; and (ii) the open-loop optimization. Let’s assume we are at the beginning of stage $l$ of the Alg. 1 with state vector $x_{l}$ at $\tau_{l}$.

2 Certainty equivalence

We use the machinery developed in Sec. 4 to compute the average of exposure at any stage $m=l,l+1,\ldots,M-1$.

From now on, for simplicity, we assume stages are based on equal partition of $[0,T]$ to $M$ segments where each has length $\Delta_{M}$. Combining Eq. (20) and $\eta_{m}(t)=\eta_{m}^{c}(t)+\eta_{m}^{v}(t)$ yields:

where $\Gamma(t)$ and $\Upsilon(t)$ are matrices independent of $u_{m}$’s and are defined as:

Note the linear relation between average exposure $\bar{\mathcal{E}}_{m}(x_{m},u_{m})$ and intervention values $u_{l},\ldots,u_{m-1}$.Let $\Gamma(k\Delta_{M})=\Gamma_{k}$ and $\Upsilon(k\Delta_{M})=\Upsilon_{k}$. Then for every $m\geq l$, Eq. (23) is rewritten as:

3 Open-loop optimization

Having found the average exposure at stages $m=l,\ldots,M-1$ we formulate an open-loop optimization to find optimal $u_{l},u_{l+1},\ldots,u_{M-1}$. Defining $\hat{u}_{l}=(u_{l};\ldots;u_{M-1})$ and $\hat{\mathcal{E}}_{l}=(\bar{\mathcal{E}}_{l}(x_{l},u_{l});\ldots;\bar{\mathcal{E}}_{M-1}(x_{M-1},u_{M-1}))$ we can aggregate Aggregating these linear forms for all $l\geq m$ yields to the following matrix equation for finding $\hat{\mathcal{E}}_{l}$:

Defining the expanded form of constraint variables as $\hat{c}_{l}=(c_{l};\ldots;c_{M-1})$, $\hat{C}_{l}=(C_{l};\ldots;C_{M-1})$, and $\hat{\alpha}_{l}=(\alpha_{l};\ldots;\alpha_{M-1})$ we have

In summary the following equation states the relation between intervention intensities given the constrains:

Then, we provide the optimization from of the above exposure shaping tasks.

For CEM consider $\hat{\beta}_{l}=(\beta_{l};\ldots,\beta_{M-1})$. Then the problem

solves CEM where $\hat{h}$ is an auxiliary vector of size $n(M-l)$.

For MEM consider the auxiliary $h$ as a vector of size $M-l$ and $\hat{h}$ a vector of size $n(M-1)$. $\hat{h}=(h(1);\ldots;h(1);h(2);\ldots,h(2);\ldots,h(M-l);\ldots;h(M-l))$ where each $h(k)$ is repeated $n$ times. Then MEM is equivalent to

For LES let $\hat{\gamma}_{l}=(\gamma_{l};\ldots;\gamma_{M-1})$ and $\hat{D}_{l}=diag(D,\ldots,D)$, then

All the three tasks involve convex (and linear) objective function with linear constraints which impose a convex feasible set. Therefore, one can use the rich and well-developed literature on convex optimization and linear programming to find the optimum intervention.

4 Scalable optimization

All the exposure shaping problems defined above require an efficient evaluation of average intensity $\eta(t)$ at all stages, which entails computing matrices $X_{l}$, $Y_{l}$, $W_{l}$, and $Z_{l}$. This leads to work with matrix exponentials and inverse matrices to obtain $\Upsilon_{m}$, and $\Gamma_{m}$ for $m=1,\ldots,M-1$. In small or medium networks, we can rely on well-known numerical methods to compute matrix exponentials and inverse. However, in large networks, the explicit computation of $X_{l}$, $Y_{l}$, $W_{l}$, and $Z_{l}$ becomes intractable. Fortunately, we can exploit the following key property of our convex campaigning framework: the average intensity itself and the gradient of the objective functions only depends on $X_{l}$, $Y_{l}$, $W_{l}$, and $Z_{l}$ (and consequently on $\Upsilon_{m}$, and $\Gamma_{m}$) through matrix-vector product operations. Similar to for the computation of the product of matrix exponential with a vector, one can use the iterative algorithm by Al-Mohy et al. , which combines a scaling and squaring method with a truncated Taylor series approximation to the matrix exponential. For solving the sparse linear system of equation, we use the well-known GMRES method, which is an Arnoldi process for constructing an $l_{2}$-orthogonal basis of Krylov subspaces. The method solves the linear system by iteratively minimizing the norm of the residual vector over a Krylov subspace. For details please refer to . Last but not least, we don’t need to explicitly build $X_{l}$, $Y_{l}$, $W_{l}$, and $Z_{l}$. At each step of gradient computation all the operations involving them are multiplication of$\Upsilon_{1},\ldots,\Upsilon_{M}$, and $\Gamma_{1},\ldots,\Gamma_{M}$ to vectors such as $u_{0},\ldots,u_{M-1}$ and $\mu$.

Temporal Properties

In this section we empirically study the theoretical results of section 4. The empirical mean and standard deviation of the intensity averaged over multiple number of cascades is compared theoretical mean. Besides this, the other purpose of the experiment is to advocate verification process in the synthetic experiments when we used simulation to evaluate the merits of the proposed algorithm and compare to the baselines. In other words, we show that the empirical activity (and hence the average exposure) is very close to its theoretical value and it is justifiable to be used for the comparison.

Fig. 2 demonstrates the activity profile of 3 random users picked in a network of 300 ones simulated 100 times to investigate theorem. 2. The setting is similar to synthetic experiment in the main paper. Piecewise exogenous intensity (interventions) are picked randomly in $[0.1,0.2]$ with a slight noise. We consider 5 stages for changing the exogenous intensity. The empirical average and standard deviation is compared to theoretical average intensity for 3 different number of runs namely, 5, 20, and 100 times. Also, Fig. 3 demonstrate the general case where the exogenous intensity is a time-varying function in theorem. 3. We take 3 sample functions to investigate this case; a sinusoidal function; an exponential decaying function with added noise; and a quadratic function.

We observe a couple of interesting facts. Firstly, it’s apparent that by increasing the number of averages the empirical intensity tends to theoretical one very fast. Secondly, as the mean becomes more accurate by increasing the number of cascades the standard deviation increases; e.g., compare the standard deviation in first and third column. Thirdly, the standard deviation is increasing with time. This is due to the fact that as time passes random elements are aggregated more and this increases variance.

Experiments

We evaluate our campaigning framework using both simulated and real world data and show that our approach significantly outperforms several baselines.

The network is generated synthetically using varying number of nodes. Initial exogenous intensity is set uniformly at random, $u_{m}^{i}\sim\mathcal{U}[0,0.1]$. Endogenous intensity coefficients (influence matrix elements) are set similarly, $a_{ij}\sim\mathcal{U}[0,0.1]$. To mimic sparse real networks half of the elements are set to 0 randomly. The matrix is scaled appropriately such that the spectral radius of the coefficient matrix is a random number smaller than one and the stability of the process is ensured.

The upper bound for the intervention intensity is set randomly from interval $\alpha^{i}\sim\mathcal{U}[0,0.1]$. The price of each person is set $c_{m}^{i}=1$, and the total budget at stage $m$ is randomly generated as $C_{m}\sim(n/10)\mathcal{U}[0,0.1]$. For the capped exposure maximization case the upper bound is set $\alpha_{m}^{i}\sim\mathcal{U}$ and target in least-squares exposure shaping is set similarly $v_{m}^{i}\sim(n/10)\mathcal{U}$. Furthermore, the shaping matrix $D$ is set to $I$. In all the synthetic experiments $\omega=0.01$ which roughly means loosing 63 % of influence after 100 units of time (minutes, hours, etc). Furthermore, the exposing matrix is set to the unweighted adjacency matrix i.e., $B_{ij}=1$ if and only if $A_{ij}\geq 10^{-4}$. This way the results are reported in terms of the exact number of exposures and are easily interpretable. In general applications any $B$ can be used for example using the influence matrix $A$ yields to a wighted exposure count. In all the synthetic and real experiments the above settings are assumed unless it is explicitly mentioned.

2 Real data description and network inference

In real data, we use a temporal resolution of one hour and selected the bandwidth $\omega=0.001$ by cross validation. Roughly speaking, it corresponds to loosing almost 50 % of the initial influence after 1 month. The upper bound for intervention intensity is set uniformly at random with mean equal to empirical intensity learned from data. The upper bound for the cap and target exposure are set similarly. For the 10 pairs of cascades we used first 3 months of data to learn the network parameters. We then drop the exogenous intensity $\mu$, and keep the influence network parameters $A$. By fixing $A$ we use the next 6 months of data to learn the exogenous intensity of sites in the two cascades at each of the $M$ stages and name them $\mu^{c_{1}}_{m}$ and $\mu^{c_{2}}_{m}$. Given $A$ we find the optimal intervention intensity $u^{opt}_{m}$ stage by stage, for each of the three exposure shaping tasks assuming $\mu=0$. Then, our prediction is: cascade $c1$ will reach a better objective value at stage $m$ if $dist(u^{opt}_{m},\mu^{c_{1}}_{m})<dist(u^{opt}_{m},\mu^{c_{2}}_{m})$ and vice versa measured by cosine similarity. The prediction accuracy is then reported as a performance measure.

3 Baselines

In this section, we describe several baselines we compare our approach. Most often, these baseline methods utilize a property to prioritize users for budget assignment.

For the capped exposure maximization problem, we consider the following four baselines:

OPL: It allocates the budget according to the solution to the dynamic programming in an open loop setting, i.e., the decisions on the allocation policy are made once and for all at the initial intervention points at initial time $t=0$. This is very important baseline to which comparison quantify the so called value of information in the context of dynamic programming and optimal control. As the name suggests it indicates how much knowing what happened so far helps making decisions for future. For the minimum and capped exposure maximization creasing $n$ the objective function is normalized by the size of network.

RND: It assigns a random point in the convex space of feasible solutions.

PRK: At each stage it subtracts the previous state ($x_{m}^{i}$) from the cap ($\alpha_{m}^{i}$) and multiply by the page rank score of the the node ($r^{i}$) computed with damping factor $0.85$ and allocates the budget proportional to this value, i.e., $u_{m}^{i}\propto\max\left((\alpha_{m}^{i}-x_{m}^{i})r^{i},0\right)$. The proposed solution is then projected to the feasible set of actions in that stage and the extra amount is redistributed similarly. The process is iterated until all the budget are allocated. This baseline assumes that more central users can leverage the total activity, therefore, assigns the budget dynamically to the more connected users proportional to their page rank score.

WEI: This baseline uses sum of out-going influence ($\,{q}^{i}=\sum_{j}a_{ji}$) as a measure of centrality of users. Similar to the previous one it assigns budget dynamically to the users proportionally to $u_{m}^{i}\propto\max\left((\alpha_{m}^{i}-x_{m}^{i})\,{q}^{i},0\right)$. This heuristic allows us to understand the effect of considering the whole network and the propagation layout with respect to only consider the direct (out-going) influence.

For the max-min exposure shaping problem, we implement the following four baselines:

OPL: Similar to the previous objective it represents the open loop solution.

RND: Similar to the previous objective it allocates the budget randomly within the feasible set.

WFL: It takes a water filling approach. It sorts the users in ascending order of the exposure in the previous stage. Then allocates budget to the first users until the the summation of its previous exposure and the allocated budget reaches the second lowest value or it violates a constraint. Then, assigns the budget to these two until they reach the third user with lowest exposure or a constraint is violated. This process is continued until the budget is allocated.

PRP: It allocates the budget inversely proportional to the the exposure at the previous stage.

For the least-square exposure shaping problem, we compare our method with four baselines:

OPL: Similar to the previous objective it represents the open loop solution.

RND: Similar to the previous objective it allocates the budget randomly within the feasible set.

GRD: It finds the difference between the exposure at previous stage ($x_{m}^{i}$ and the target from $v$ and sorts them decreasingly. Then, allocates budget one at a time until a constraint is violated. It iterates over the users until the budget is fully allocated.

REL: Similar to the above finds the difference from the target but allocates the budget proportionally, i.e., $u_{m}^{i}\propto\max\left((v^{i}-x_{m}^{i}),0\right)$ for all users. If one allocation violates a constraint the extra amount is reallocated in the same manner.

4 Campaigning results on synthetic networks

In this section, we experiment with a synthetic network of $300$ nodes. We focus on three tasks: capped exposure maximization, minimax exposure shaping, and least square exposure shaping. To compare the methods we simulate the network with the prescribed intervention intensity and compute the objective function based on the events happened during the simulation. The mean and standard deviation of the objective function out of 10 runs are reported.

Fig. 4 summarizes the performance of the proposed algorithm (CLL) and 4 other baselines on different campaigning tasks. For CEM, our approach consistently outperforms the others by at least 10. This means it exposes each user to the campaign at least 10 times more than the rest consuming the same budget and within the same constraints. The extra 20 units of exposures of over OPL or value of information shows how much we gain by incorporating a dynamic closed-loop solution as opposed to open-loop one-time optimization over all stages. For MEM, the proposed method outperforms the others by a smaller margin, however, the 0.1 exposure difference with the second best method is not trifling. This is expected as lifting the minimum exposure is a difficult task . For LES, results demonstrate the superiority of CLL by a large margin. The $10^{3}$ difference with the second best algorithm aggregated over 6 stages roughly is translated to $\sqrt{10^{3}/6}\sim 13$ difference in the number of exposures per user. Given the heterogeneity of the network activity and target shape, this is a significant improvement over the baselines. Appendix LABEL:appen-synth includes further results on varying number of nodes, number of stages, and duration of each stage.

5 Campaigning results on real world networks

We also evaluate the proposed framework on real world data. To this end, we utilize the MemeTracker dataset which contains the information flows captured by hyperlinks between different sites with timestamps during 9 months. This data has been previously used to validate Hawkes process models of social activity . For the real data, we utilize two evaluation procedures. First, similar to the synthetic case, we simulate the network, but now on a network based on the learned parameters from real data. However, the more interesting evaluation scheme would entail carrying out real intervention in a social media platform. Since this is very challenging to do, instead, in this evaluation scheme we used held-out data to mimic such procedure. Second, we form 10 pairs of clusters/cascades by selecting any 2 combinations of 5 largest clusters in the Memetracker data. Each is a cascade of events around a common subject. For any of these 10 pairs, the methods are faced to the question of predicting which cascade will reach the objective function better. They should be able to answer this by measuring how similar their prescription is to the real exogenous intensity. The key point here is that the real events happened are used to evaluate the objective function of the methods. Then the results are reported on average prediction accuracy on all stages over 10 runs of random constraint and parameter initialization on 10 pairs of cascades.

Fig. 5, left column illustrates the performance with respect to increasing the number of users in the network. The performance drops slightly with the network size. This means that prediction becomes more difficult as more random variables are involved. The middle panel shows the performance with respect to increasing the number of intervention points. Here, a slight increase in the performance is apparent. As the number of intervention points increases the algorithm has more control over the outcome and can reach the objective function better.

Fig. 5 top row summarizes the results of CEM. The left panel demonstrates the predictive performance of the algorithms. CLL consistently outperforms the rest. With 65-70 % of accuracy in predicting the optimal cascade. The right panel shows the objective function simulated 10 times with the learned parameters for network of $n=300$ users on $6$ intervention points. The extra 2.5 extra exposure per user compared to the second best method with the same budget and constraint would be a significant advertising achievement. Among the competitors OPL and RND seem to perform good. If there where no cap over the resultant exposure, all methods would perform comparably because of the linearity of sum of exposure. However, the successful method is the one who manage to maximize exposure considering the cap. Failure of PRK and WEI indicates that structural properties are not enough to capture the influence. Compared to these two, RND performs better in average, however exhibits a larger variance as expected.

Fig. 5 middle row summarizes the results for MEM and shows CLL outperforms others consistently. CLL still is the best algorithm and OPL and RND are the significant baselines. Failure of WFL and PRP shows the network structure plays a significant role in the activity and exposure processes.

The bottom row in Fig. 5 demonstrates the results of LES. CLL is still the best method. Among the competitors, OPL is still strong but RND is not performing well for this task. The objective function is summation of the square of the gap between target and current exposure. This explains why GRD is showing a comparable success, since, it starts with the highest gap in the exposure and greedily allocates the budget.

Related Work

Exposure shaping problems are significantly more challenging than traditional influence maximization problems, which aim to identify a set of users who influence others in the network and trigger a large cascade of adoptions . First, in influence maximization, the state of each user is often assumed to be binary. However, such assumption does not capture the recurrent nature of social activity. Second, while influence maximization methods identify a set of users to provide incentives, they do not typically provide a quantitative prescription on how much incentive should be provided to each user. Third, exposure shaping concerns about a larger variety of target states, such as minimum exposure requirement and homogeneity, not just maximization.

Existing work in stochastic optimal control includes jump diffusion stochastic differential equations (SDE) which focuses on controlling the SDEs with the jump term driven by Poisson processes not for Hawkes processes. Inspired by the opinion dynamics model proposed in , the authors in proposes a multivariate jump diffusion process framework for modeling opinion dynamics over networks and determining the control over such networks.

In , a continuous action iterated prisoners’ dilemma was used to model the interactions in a social network and extended by incorporating a mechanism for external influence on the behavior of individual nodes. Markov Decision Process (MDP) framework is proposed to develop several scheduling algorithms for optimal control of information epidemics with susceptible-infected (SI) model on Erdős-Rényi and scale-free networks . In , the authors provided an analytically tractable model for information dissemination over networks and solved the optimal control signal distribution time for minimizing the accumulated network cost via dynamic programming. Furthermore, formulated the maximization of spread of a given message in the population within the stipulated time as continuous-time deterministic optimal control problem.

In contrast, our work has been built on the well-developed theory of point processes . Their usage in modeling activity in social network is becoming increasingly popular . More specifically, we utilizes the Hawkes process which its self-exciting property has been proved to be an appropriate choice in modeling processes of and on the networks: model and infer the social activity in networks Based on Hawkes process assumption of activity in social networks study one or several phenomena in the social network. In authors proposed a broadcasting algorithm to maximize the visibility of posts in Twitter. It only consider the direct followers and does not involve peer influence in propagation process. Our work is closely related to , which is extended in two significant directions here: First, we generalize their result on driving a time-dependent average intensity in the case where the exogenous intensity is not constant. Second, instead of one-shot optimization we pose the problem as a multi-stage optimal control problem which is more fit to real world applications. Then we propose a dynamic programming solution to the multi-stage optimization problem.

Conclusion and Future work

In this paper, we introduced the optimal multistage campaigning problem, which is a generalization of the activity shaping and influence maximization problems, and it allows for more elaborate goal functions. Our model of social activity is based on multivariate Hawkes process, and for the first time, we manage to derive a linear connection between a time-varying exogenous intensity (i.e., the part that can be easily manipulated via incentives) and the overall network exposure of the campaign. The multistage optimal control problem is introduced and an approximate closed-loop dynamic programming approach is proposed to find the optimal interventions. This linear connection between exogenous intensity and campaign’s exposure enables developing a convex optimization framework for exposure shaping, deriving the necessary incentives to reach a global exposure pattern in the network. The method is evaluated on both synthetic and real-world held-out data and is shown to outperform several heuristics.

Experiments on synthetic and real world datasets reveal a couple of interesting facts:

Most notable lesson is the presence of the so-called value of information. We have witnessed, both in synthetic and real dataset, it is possible to achieve lower cost, essentially by taking advantage of extra information. If the information was not available the controller couldn’t adapt appropriately to the unexpected behavior and consequently the cost could have been adversely affected.

What we have empirically observed is that the performance, measured in achieving the lower cost and accurate prediction, improves with increasing the number of intervention points. The more control over social network the better one can steer the campaign towards a goal.

The performance slightly decreases with increasing the number of nodes. That might be due to the increased dimensionality of the optimization problem.

We acknowledge that our method has indeed limitations. For the networks at the scale of web or large social networks faster and scalable methods need to be explored and developed which remains as future works. There are many other interesting venues for future work too. For example, considering competing/collaborating campaigns and their equilibria and interactions, a continuous-time intervention scheme, and exploring other approximate dynamic programming approaches remain as future work.

References

Appendix A Proofs

In particular, if $\Phi(t)=Ae^{-\omega t}\mathbf{1}_{\geq 0}(t)=[a_{ij}e^{-\omega t}\mathbf{1}_{\geq 0}(t)]_{ij}$ where $0\leq\omega\notin\text{Spectrum}(A)$, then

for $t\in[0,T]$, where, $\mathbf{1}_{\geq 0}(t)$ is an indicator function for $t\geq 0$.

Let $\Psi(t)$ satisfy (34) and $\mu(t)$ be a right-continuous piecewise constant intensity function of form (10), then the rate function $\eta(t)$ is given by

for all $t\in(\tau_{m-1},\tau_{m}]$ and $m=1,\dots,M$, where $c_{-1}:=0$ by convention.

for all $t\in[0,T]$. This result can by verified easily for $t\in[0,\tau]$. If $t\in(\tau,T]$, then $\hat{\mu}(t)=\mu(t)+(c-c_{M})\mathbf{1}_{(\tau,T]}(t)=\mu(t)+(c-c_{M})$ and

where we used the fact that $\eta(t)$ is the rate function for intensity $\mu(t)$ to get the second equality, applied change of variables $u=s-\tau$ to obtain the third equality, and the property (34) of $\Psi(t)$ to get the fourth equality. This implies that the rate function is $\hat{\eta}(t)$ given in (37) for the updated piecewise constant intensity $\hat{\mu}(t)$ with $M+1$ partitions, and hence completes the proof. ∎

If $\Psi\in C^{1}([0,T])$ and satisfies (34), and exogenous intensity $\mu$ is bounded and piecewise absolutely continuous on $[0,T]$ where $\mu(t+)=\mu(t)$ at all discontinuous points $t$, then $\mu$ is differentiable almost everywhere, and the semi-indefinite integral

It suffices to show (40) for absolutely continuous $\mu(t)$ on $[0,T)$ since extending the proof to piecewise absolutely continuous function is straightforward. We first define $\mu(T)=\mu(T-)$ and obtain a continuous $\mu(t)$ on $[0,T]$. Since $[0,T]$ is compact, we know $\mu(t)$ is uniformly continuous, and hence there exists a sequence of piecewise constant functions $\{\mu_{k}\}_{k=1}^{\infty}$ such that $\mu_{k}\to\mu$ uniformly on $[0,T]$, i.e., $\lim_{k\to\infty}\sup_{0\leq t\leq T}|\mu_{k}(t)-\mu(t)|=0$ [37, Thm. 2.3.6] This also implies that $\{\mu_{k}\}$ is uniformly bounded. For every $k$, piecewise constant function $\mu_{k}$ has bounded variation, therefore we have by [38, Thm. 3.36] that

for all $t\in[0,T]$. Since $\Psi\in C^{1}$ we know $\Psi^{\prime}$ is continuous and bounded on $[0,T]$. By Lebesgue’s bounded convergence theorem we know

Furthermore, using the uniform convergence of $\{\mu_{k}\}$ to $\mu$, we know the right hand side (41) converges to $\int_{0}^{t}\Psi^{\prime}(t-s)\mu(s)ds+\Psi(0)\mu(t)-\Psi(t)\mu(0)$. Then integration by parts for piecewise absolutely continuous function $\mu$ which has bounded variation implies that $\eta(t)=\int_{0}^{t}\Psi(t-s)d\mu(s)$ for all $t\in[0,T]$. ∎

Suppose $\Psi$ and $\mu$ satisfy the same conditions as in Thm. 3, and define $\psi=\Psi^{\prime}$, then the rate function is $\eta(t)=(\psi*\mu)(t)$. In particular, if $\Phi(t)=Ae^{-\omega t}\mathbf{1}_{\geq 0}(t)=[a_{ij}e^{-\omega t}\mathbf{1}_{\geq 0}(t)]_{ij}$ then the rate function $\eta(t)=A\int_{0}^{t}e^{(A-wI)(t-s)}\mu(s)ds$.

Appendix B Extended synthetic results

For the synthetic case we can freely evaluate the properties of the proposed algorithm under several conditions. We assess the performance of the algorithm and compare to the baselines in three settings: i) increasing size of the network; ii) increasing number of intervention points; iii) increasing the time window (or equivalently the stage duration). The results are reported while keeping other parameters fixed. To compare it to the others we simulate the network with the prescribed intervention intensity and compute the objective function. The mean and standard deviation of the objective function out of 10 runs are reported.

Figures 6, 7, and 8 shows the results for CEM, MEM, and LES respectively. In each figure, the first row is for varying number of nodes, the second row is for varying number of intervention points, and the third row is for varying duration of stages. The proposed method is consistently better than the baselines. The trends and facts reported in the main paper are observed in this extended experiment. Additionally, we want to refer the high variance of baseline methods especially RND and OPL which is what we expect.