RedQueen: An Online Algorithm for Smart Broadcasting in Social Networks

Introduction

Whenever a user in an online social network decides to share a new story with her followers, she is often competing for attention with dozens, if not hundreds, of stories simultaneously shared by other users that their followers follow . In this context, recent empirical studies have shown that stories at the top of their followers’ feed are more likely to be noticed and consequently liked or shared . Can we find an algorithm that helps a user decide when to post to increase her chances to stay at the top?

The “when-to-post” problem was first studied by Spasojevic et al. , who performed a large empirical study on the best times to post in Twitter and Facebook, measuring attention a user elicits by means of the number of responses to her posts. Moreover, they designed several heuristics to pinpoint at the times that elicit the greatest attention in a training set and showed that these times also lead to more responses in a held-out set. Since then, algorithmic approaches to the “when-to-post” problem with provable guarantees have been largely lacking. Only very recently, Karimi et al. introduced a convex optimization framework to find optimal broadcasting strategies, measuring attention a user elicits as the time that at least one of her posts is among the $k$ most recent stories received in her followers’ feed. However, their algorithm requires expensive data pre-processing, it does not adapt to changes in the users’ feeds dynamics, and in practice, it is less effective than our proposed algorithm, as shown in Section 5.

In this paper, we design a novel online algorithm for the when-to-post problem, where we measure visibility of a broadcaster as the position of her most recent post on her followers’ feeds over time. A desirable property of this visibility measure is that it can be easily extracted from real data without actual interventions — given any particular broadcasting strategy for a user, one can always measure its visibility using a separate held-out set of the user’s followers’ feeds . In contrast, measures based on users’ reactions (e.g., number of likes, shares and replies) are difficult to estimate from real data, due to the presence of other confounding factors such as users’ influence, content and wording .

More precisely, we represent users’ posts and feeds using the framework of temporal point processes, which characterizes the continuous time interval between posts using conditional intensity functions . Under this representation, finding the optimal broadcasting (or posting) strategy for a user reduces to finding its associated conditional broadcasting intensity . Then, for a large family of intensity functions, which includes Hawkes and Poisson as particular instances, we find “when-to-post” by solving a novel optimal control problem for a system of jump stochastic differential equations (SDEs) . Our problem formulation differs from previous literature in two key technical aspects, which are of independent interest:

The control signal is a conditional (broadcasting) intensity, which is used to sample stochastic events (i.e., stories to post). As a consequence, the problem formulation requires another layer of stochasticity. In previous work, the control signal is a time-varying real vector.

The (broadcasting) intensities are stochastic Markov processes and thus the dynamics are doubly stochastic. This requires us to redefine the cost-to-go to incorporate the instantaneous value of these intensities as additional arguments. Previous work has typically considered constant intensities and only very recently time-varying deterministic intensities .

These technical aspects have implications beyond the smart broadcasting problem since they enable us to establish a previously unexplored connection between optimal control of jump SDEs and double stochastic temporal point processes (e.g., Hawkes processes), which have been increasingly used to model social activity .

Moreover, we find that the solution to the above optimal control problem is surprisingly simple: the optimal broadcasting intensity for a user is given by the position of her most recent post on each of her follower’s feeds. This solution allows for a simple and highly efficient online procedure to sample the optimal times for a user to broadcast, which can be implemented in a few lines of code and does not require fitting a model for the feeds’ intensities. Finally, we performed experiments on both synthetic and real data gathered from Twitter and show that our algorithm is able to consistently make a user’s posts stay at the top of her followers’ feeds, is robust to changes on the dynamics (or volume) of her followers’ feeds, and significantly outperforms the state of the art .

Further related work. In addition to the paucity of work on the when-to-post problem , discussed previously, our work also relates to: (i) empirical studies on attention and information overload in social and information networks , which investigate whether there is a limit on the amount of ties (e.g., friends, followees or phone contacts) people can maintain, how people distribute attention across them, and how attention influences the propagation of information; and (ii) the influence maximization problem , which aims to find a set of nodes in a social network whose initial adoption of a certain idea or product can trigger the largest expected number of follow-ups. In contrast, we focus on optimizing a social media user’s broadcasting strategy to capture the greatest attention from the followers.

Preliminaries

We first revisit the framework of temporal point processes and then use it to represent broadcasters and feeds in social and information networks.

A temporal point process can also be represented as a counting process $N(t)$, which is the number of events up to time $t$. Moreover, given $\mathcal{H}(t)=\{t_{i}\in\mathcal{H}\,|\,t_{i}<t\}$, the history of event times up to but not including time $t$, we can characterize the counting process using the conditional intensity function $\lambda^{*}(t)$, which is the conditional probability of observing an event in an infinitesimal window $[t,t+dt)$ given the history $\mathcal{H}(t)$, i.e.,

where $dN(t)\in\{0,1\}$ and the sign ∗ means that the intensity may depend on the history $\mathcal{H}(t)$.

The functional form for the intensity is often chosen to capture the phenomena of interest. For example, in the context of modeling social activity, retweets have been modeled using Hawkes processes and daily and weekly variations on the volume of posted tweets have been captured using Poisson processes . In this work, we consider the following general functional form, which includes Hawkes and Poisson as particular instances:

Let $N(t)$ be a counting process with an associated intensity $\lambda^{*}(t)$ given by Eq. 1. Then the tuple $(N(t),\lambda^{*}(t))$ is a doubly stochastic Markov process, whose dynamics can be defined by the following jump SDE:

with initial condition $\lambda^{*}(0)=\lambda_{0}(0)$.

In the remainder of the paper, to simplify the notation, we drop the sign ∗ from the intensities.

Given the adjacency matrix $A\in\{0,1\}^{n\times n}$, where $A_{ij}=1$ indicates that user $j$ follows user $i$, we can represent the times of the stories users receive in their feeds from the broadcasters they follow as a sum of counting processes, $A^{T}\bm{N}(t)$, and calculate the corresponding conditional intensities as $\bm{\gamma}(t)=A^{T}\bm{\mu}(t)$. Here, we denote the history of times of the stories received by user $j$ by time $t$ as $\mathcal{F}_{j}(t):=\cup_{i\in\mathcal{N}(j)}\mathcal{H}_{i}(t)$, where $\mathcal{N}(j)$ is the set of users that $j$ follows.

Finally, from the perspective of a broadcaster $i$, it is useful to define the counting processes $\bm{M}_{{\scriptscriptstyle\setminus}i}(t)=A^{T}\bm{N}(t)-A_{i}N_{i}(t)$, in which the $j$-th dimension, $M_{j{\scriptscriptstyle\setminus}i}(t)$, represents the times of the stories user $j$ receives due to other broadcasters she follows, and $A_{i}$ is the $i$-th row of the adjacency matrix $A$. Moreover, for each of these counting processes, the conditional intensity is given by $\gamma_{j{\scriptscriptstyle\setminus}i}(t)=\gamma_{j}(t)-\mu_{i}(t)$ and the history is given by $\mathcal{F}_{j{\scriptscriptstyle\setminus}i}(t):=\mathcal{F}_{j}(t)\backslash\mathcal{H}_{i}(t)$.

Problem Formulation

In this section, we first define our visibility measure, $r(t)$, then derive a jump stochastic differential equation that links our measure to the counting processes associated to a broadcaster and her followers, and conclude with a statement of the when-to-post problem for our visibility measure.

Definition of visibility. Given a broadcaster $i$ and one of her followers $j$, we define the visibility function $r_{ij}(t)$ as the position or rank of the most recent story posted by $i$ in $j$’s feed by time $t$, which clearly depends on the feed ranking mechanism in the corresponding social network. Here, for simplicity, we assume each user’s feed ranks stories in inverse chronological orderAt the time of writing, Twitter and Weibo rank stories in inverse chronological order by default and Facebook allows choosing such an ordering.. However, our framework can be easily extended to any feed ranking mechanisms, as long as its rank dynamics can be expressed as a jump SDEThis would require either having access to the corresponding feed ranking mechanism or reverse engineering it, which is out of the scope of this work..

Under the inverse chronological ordering assumption, position is simply the number of stories that others broadcasters posted in $j$’s feed from the time of the most recent story posted by $i$ until $t$. Then, when a new story arrives to a user’s feed, it appears at the top of the feed and the other stories are shifted down by one. If we identify the time of the most recent message posted by $i$ by time $t$ as $\tau_{i}(t)=\max\{t_{k}\in\mathcal{H}_{i}(t)\}$, then the visibility is formally defined as:

Note that, if the last story posted by $i$ is at the top of $j$’s feed at time $t$, then $r_{ij}(t)=0$.

Dynamics of visibility. Given a broadcaster $i$ with broadcasting counting process $N_{i}(t)$ and one of her followers $j$ with feed counting process due to other broadcasters $M_{j{\scriptscriptstyle\setminus}i}(t)$, the rank of $i$ in $j$’s feed $r_{ij}(t)$ satisfies the following equation:

where each term models one of the three possible situations:

The other broadcasters post a story in $(t,t+dt]$, $dM_{j{\scriptscriptstyle\setminus}i}(t)=1$, and broadcaster $i$ does not post, $dN_{i}(t)=0$. The position of the last story posted by $i$ in $j$’s feed steps down by one, i.e., $r_{ij}(t+dt)=r_{ij}(t)+1$.

Broadcaster $i$ posts a story in $(t,t+dt]$, $dN_{i}(t)=1$, and the other broadcasters do not, $dM_{j{\scriptscriptstyle\setminus}i}(t)=0$. No matter what the previous rank was, the new rank is $r_{ij}(t+dt)=0$ since the newly posted story appears at the top of $j$’s feed.

No one posts any story in $(t,t+dt]$, $dN_{i}(t)=0$ and $dM_{j{\scriptscriptstyle\setminus}i}(t)=0$. The rank remains the same, i.e., $r_{ij}(t+dt)=r_{ij}(t)$

We skip the case in which $M_{j{\scriptscriptstyle\setminus}i}(t)=1$ and $dN_{i}(t)=1$ in the same time interval $(t,t+dt]$ because, by the Blumenthal zero-one law , it has zero probability. Now, by rearranging terms and using that $dN_{i}(t)dM_{j{\scriptscriptstyle\setminus}i}(t)=0$, we uncover the following jump SDE for the visibility (or rank) dynamics:

where $dr_{ij}(t)=r_{ij}(t+dt)-r_{ij}(t)$. Figure 1 illustrates the concept of visibility for one broadcaster and one follower.

where $u(t_{0},t_{f}]$ denotes user $i$’s intensity from $t_{0}$ to $t_{f}$, the expectation is taken over all possible realizations of the counting processes associated to user $i$ and all other broadcasters from $t_{0}$ to $t_{f}$, denoted as $(N_{i},\bm{M}_{{\scriptscriptstyle\setminus}i})(t_{0},t_{f}]$, and $\phi(\bm{r}(t_{f}))$ is an arbitrary penalty functionThe final penalty function $\phi(\bm{r}(t_{f}))$ is necessary to derive the optimal intensity $u^{*}(t)$ in Section 4. However, the actual optimal intensity $u^{*}(t)$ does not depend on the particular choice of terminal condition.. Here, by considering a nondecreasing loss, we penalize times when the position of the most recent story on each of the follower’s feeds is high (i.e., the most recent story does not stay at the top) and we limit the number of stories the broadcaster can post. Finally, note that the optimal intensity $u(t)$ for broadcaster $i$ at time $t$ may depend on the visibility $\bm{r}(t)$ with respect to each of her followers and thus the associated counting process $N_{i}(t)$ may be doubly stochastic.

Stochastic Optimal Control Algorithm

In this section, we tackle the when-to-post problem defined by Eq. 3 from the perspective of stochastic optimal control of jump SDEs . More specifically, we first derive a solution to the problem considering only one follower, provide an efficient practical implementation of the solution and then generalize it to the case of multiple followers. We conclude this section by deriving a solution to the problem given an (idealized) oracle that knows the times of all stories in the followers’ feeds a priori, which we will use as baseline.

Optimizing for one follower. Given a broadcaster $i$ with $N_{i}(t)=N(t)$ and $\mu_{i}(t)=u(t)$ and only one of her followers $j$ with $M_{j{\scriptscriptstyle\setminus}i}(t)=M(t)$ and $\gamma_{j{\scriptscriptstyle\setminus}i}(t)=\lambda(t)$, we can rewrite the when-to-post problem defined by Eq. 3 as

where, using Eq. 2 and Eq. 4, the dynamics of $M(t)$ and $r(t)$ are given by the following two coupled jump SDEs:

with initial conditions $r(t_{0})=r_{0}$ and $\lambda(t_{0})=\lambda_{0}$, and the dynamics of $N(t)$ are given by the intensity $u(t)$ that we aim to optimize. The above stochastic optimal control problem differs from previous literature in two key technical aspects, which require careful reasoning:

The control signal $u(t)$ is a conditional intensity, which controls the dynamics of the counting process $N(t)$ (i.e., number of stories broadcasted by user $i$ by time $t$). As a consequence, the problem formulation needs to account for another layer of stochasticity. Previous work assumes the control signal to be a time-varying real vector.

The dynamics of the counting process $M(t)$ (i.e., number of stories broadcasted by other users that $j$ follows by time $t$) are doubly stochastic Markov. Previous work has typically considered memoryless Poisson processes and, only very recently, inhomogeneous Poisson .

Next, we will define a novel optimal cost-to-go function that accounts for the above unique aspects of our problem, showing that the Bellman’s principle of optimality still follows, and finally find the optimal solution using the corresponding Hamilton-Jacobi-Bellman (HJB) equation.

The optimal cost-to-go $J(r(t),\lambda(t),t)$ is defined as the minimum of the expected value of the cost of going from state $r(t)$ with intensity $\lambda(t)$ at time $t$ to final state at time $t_{f}$, i.e.,

where the expectation is taken over all trajectories of the control and noise jump process, $N$ and $M$, in the $(t,t_{f}]$ interval, given the initial values of $r(t)$, $\lambda(t)$ and $u(t)$.

To find the optimal control $u(t,t_{f}]$ and cost-to-go $J$, we break the problem into smaller subproblems, using the Bellman’s principle of optimality, which the above definition allows (proven in Appendix):

The optimal cost satisfies the following recursive equation:

where the expectation is taken over all trajectories of the control and noise jump processes, $N$ and $M$, in $(t,t+dt]$. Then, we use the Bellman’s principle of optimality to derive a partial differential equation on $J$, often called the Hamilton-Jacobi-Bellman (HJB) equation . To do so, we first assume $J$ is continuous and then rewrite Eq. 8 as

Then, we differentiate $J$ with respect to time $t$, $r(t)$ and $\lambda(t)$ using Lemma 6 (refer to Appendix).

Specifically, consider $x(t)=r(t)$, $y(t)=\lambda(t)$ and $F=J$ in the above mentioned lemma, then,

Next, if we plug in the above equation in Eq. 9, it follows that

where $s(t)$ is a time significance function $s(t)\geq 0$, which favors some periods of times (e.g., times in which the follower is onlineSuch information may be hidden but one can use the followers’ posting activity or geographic location as a proxy .), and $q$ is a given parameter, which trade-offs visibility and number of broadcasted posts.

Under these definitions, we take the derivative with respect to $u(t)$ of Eq. 11 and uncover the relationship between the optimal intensity and the optimal cost:

Finally, we substitute the above expression in Eq. 11 and find that the optimal cost $J$ needs to satisfy the following nonlinear differential equation:

with $J(r(t_{f}),\lambda(t_{f}),t_{f})=\phi(r(t_{f}))$ as the terminal condition. The following lemma provides us with a solution to the above equation (proven in Appendix):

Any solution to the nonlinear differential equation given by Eq. 13 can be approximated as closely as desired by

where $f(t)$ and $g_{j}(t)$ are time-varying functions, and $m$ controls for the approximation guarantee.

Given the above Lemma and Eq. 12, the optimal intensity is readily given by following theorem:

The optimal intensity for the when-to-post problem defined by Eq. 6 with quadratic loss and penalty function is given by $u^{*}(t)=\sqrt{{s(t)}/{q}}\,r(t)$.

The optimal intensity only depends on the position of the most recent post by user $i$ in her follower’s feed and thus allows for a very efficient procedure to sample posting times, which exploits the superposition theorem . The key idea is as follows: at any given time $t$, we can view the process defined by the optimal intensity as a superposition of $r(t)$ inhomogeneous poisson processes with intensity $\sqrt{{s(t)}/{q}}\,r(t)$ which starts at jumps of the rank $r(t)$, and find the next sample by computing the minimum across all samples from these processes. Algorithm 1 summarizes our (sampling) method, which we name RedQueen . Within the algorithm, $othersNextPost(\,)$ returns the time of the next event by other broadcasters in the followers’ feeds, once the events happens. In practice, we only need to know if the event happens before we post. Remarkably, it only needs to sample $M(t_{f})$ times from a (exponential) distribution (if significance is constant) and requires $O(1)$ space.

Optimizing for multiple followers. Given a broadcaster $i$ with $N_{i}(t)=N(t)$ and $\mu_{i}(t)=u(t)$ and her followers $\mathcal{N}(i)$ with $\bm{M}_{{\scriptscriptstyle\setminus}i}(t)=\bm{M}(t)$ and $\bm{\gamma}_{{\scriptscriptstyle\setminus}i}(t)=\bm{\lambda}(t)$, the dynamics of $\bm{M}(t)$ and $\bm{r}(t)$, which we need to solve Eq. 3, are given by:

where $\odot$ is the element-wise product and $\bm{\alpha}=[\alpha_{1},\cdots,\alpha_{n}]^{T}$ and $\bm{w}=[w_{1},\cdots,w_{n}]^{T}$ are the parameters defining each of the followers’ feed dynamics, and $n=|\mathcal{N}(i)|$ is the number of followers.

where $s_{i}(t)$ is the time significance function for follower $i$, as defined above, and $q$ is a given parameter. Then, proceeding similarly as in the case of one follower, we can show that:

which only depends on the position of the most recent post by user $i$ in her followers’ feeds. Finally, we can readily adapt RedQueen (Algorithm 1) to efficiently sample the posting times using the above intensity – it only needs to sample $|\cup_{j\in\mathcal{N}(i)}\mathcal{F}_{j\backslash i}(t_{f})|$ values and requires $O(|\mathcal{N}(i)|)$ space.

Optimizing with an oracle. In this section, we consider a broadcaster $i$ with $N_{i}(t)=N(t)$ and $\mu_{i}(t)=u(t)$, only one of her followers $j$ with $M_{j{\scriptscriptstyle\setminus}i}(t)=M(t)$, and a constant significance $s(t)=s$. The derivation can be easily adapted to the case of multiple followers and time-varying significance.

Suppose there is an (idealized) oracle that reveals $M(t)$ from $t_{0}$ to $t_{f}$, i.e., the history $\mathcal{F}_{j{\scriptscriptstyle\setminus}i}(t_{f})=\mathcal{F}(t_{f})$ is given, and $M(t_{f})=|\mathcal{F}(t_{f})|=m$. Then, we can rewrite Eq. 3 as

where the expectation is only taken over all possible realizations of the counting process $N(t_{0},t_{f}]$ since $M(t_{0},t_{f}]$ is revealed by the oracle and thus deterministic.

where $w_{i}=t_{i}-t_{i-1}$. Next, we can break the minimization and use Bellman’s principle of optimality,

and, since $u_{k}\in\{0,1\}$, the above recursive equation can be written as

Finally, we can find the optimal control $u^{*}_{k},\,k=0,\ldots,m$ and cost $J(r_{0},0)$ by backtracking from the terminal condition $J(r_{m+1},m+1)=r_{m+1}^{2}/2$ to the initial state $r_{0}$, as summarized in Algorithm 2, which can be adapted to multiple followers. Note that, in this case, the optimal strategy is not stochastic and consists of a set of optimal posting times, as one could have guessed. However, for multiple followers, the complexity of the algorithm is $O(m^{2})$, where $m=|\cup_{j\in\mathcal{N}(i)}\mathcal{F}_{j\backslash i}(t_{f})|$.

Experiments

Optimizing for one follower. We first experiment with one broadcaster and one follower against an increasing number of events (or budget). We generate the counting processes $M(t)$ due to other broadcasters using Hawkes processes, which are particular instances of the general functional form given by Eq. 1. We perform $10$ independent simulation runs and compute the average and standard error (or standard deviation) of the quality measures. Fig. 2 summarizes the results, which show that our method: (i) consistently outperforms the method by Karimi et al. by large margins; (ii) achieves at most $3$$\times$ higher position over time than the oracle as long as the budget is $<$$30$% of the posted events by all other broadcasters; and, (iii) achieves $>$$40$% of the value of time at the top that the oracle achieves.

Optimizing for multiple followers. Next, we experiment with one broadcaster and multiple followers. In this case, we generate the counting processes $M(t)$ due to other broadcasters using piece-constant intensity functions. More specifically, we simulate the feeds of each follower for $1$ day, using $24$ $1$-hour long segments, where the rate of posts remains constant per follower in each segment and the rate itself varies as a half-sinusoid (i.e., from $\sin{0}$ to $\sin{\pi}$), with each follower starting with a random initial phase. This experimental setup reproduces volume changes throughout the day across followers’ feeds in different time-zones and closely resembles the settings in previous work . The total number of posts by the RedQueen broadcaster is kept nearly constant and is used as the budget for the other baselines. Additionally, for Karimi’s method, we provide as input the true empirical rate of tweets per hour for each user. Here, we do not compare with the oracle since, due to its quadratic complexity, it does not scale.

Figure 3 summarizes the results. In terms of position over time, RedQueen outperforms Karimi’s method by a factor of $2$. In terms of time at the top, RedQueen achieves $\sim$18% lower values than Karimi’s method for $1$-$4$ followers but $\sim$10% higher values for $>$$5$ followers. A potential reason for Karimi’s method to performs best in terms of time at the top for a low number of followers and piecewise constant intensities is that, while the number of followers is low, there are segments which are clearly favorable and thus Karimi’s method concentrates posts on those, however, as the number of followers increases, there are no clear favorable segments and thus advance planning does not give Karimi’s method any advantage. On the other hand, RedQueen, due to its online nature, is able to adapt to transient variations in the feeds.

2 Experiments on real data

Dataset description and experimental setup. We use data gathered from Twitter as reported in previous work , which comprises profiles of $52$ million users, $1.9$ billion directed follow links among these users, and $1.7$ billion public tweets posted by the collected users. The follow link information is based on a snapshot taken at the time of data collection, in September 2009. Here, we focus on the tweets published during a two month period, from July 1, 2009 to September 1, 2009, in order to be able to consider the social graph to be approximately static, and sample $2000$ users uniformly at random as broadcasters and record all the tweets they posted. Then, for each of these broadcasters, we track down their followers and record all the (re)tweets they posted as well as reconstruct their timelines by collecting all the (re)tweets published by the people they follow. We assign equal significance to each follower but filter out those who follow more than $500$ people since, otherwise, they would dominate the optimal strategy. Finally, we tune $q$ such that the total number of tweets posted by our method is equal to the number of tweets the broadcasters tweeted during the two month period (with a tolerance of $10\%$).

Solution quality. We only compare the performance of our method against the method by Karimi et al. since the oracle does not scale to the size of real data. Moreover, for the method by Karimi et al., we divide the two month period into ten segments of approximately one week to fit the piecewise constant intensities of the followers’ timelines, which the method requires. Fig. 4 summarizes the results by means of box plots, where position over time and time at the top are normalized with respect to the value achieved by the broadcasters’ actual true posts during the two month period. That means, if $y=1$, the optimized intensity achieves the same position over time or time at the top as the broadcaster’s true posts. In terms of position over time and time at the top, RedQueen consistently outperforms competing methods by large margins and achieves $0.28$$\times$ lower average position and $3.5$$\times$ higher time at the top, in average, than the broadcasters’ true posts – in fact, it achieves lower position over time (higher time at the top) for $100$% ($99.1$%) of the users.

Time significance. We look at the actual broadcasting strategies for one real user and investigate the effect of a time varying significance. We define $s_{i}(t)$ to be the probability that follower $i$ is online on that weekday, estimated empirically using the (re)tweets the follower posted as in Karimi et al. . Fig. 5 compares the position over time for the most recent tweet posted by a real user against the most recent one posted by a simulation run of RedQueen with and without time varying significance. We can see that without significance information, RedQueen posts at nearly an even pace. However, when we supply empirically estimated significance, RedQueen avoids tweeting at times the followers are unlikely to be active, i.e., the weekends, denoted by the shaded areas in panel (c) of Fig. 5. Due to this, the average position (maximum position) falls from $389{.}45$ ($1085{.}17$) to $425{.}25$ ($1431{.}0$), but is still lower than $698{.}04$ ($2597{.}9$) obtained by the user’s original posting schedule.

Conclusions

In this paper, we approached the when-to-post problem from the perspective of stochastic optimal control and showed that the optimal broadcasting strategy is surprisingly simple – it is given by the position of her most recent post on each of her follower’s feed. Such a strategy can be implemented using a simple and efficient on-line algorithm. We experimented with synthetic and real-world data gathered from Twitter and showed that our algorithm consistently makes a user’s posts more visible over time and it significantly outperforms the state of the art.

Our work also opens many venues for future work. For example, in this work, we considered social networks that sort stories in the users’ feeds in inverse chronological order (e.g., Twitter, Weibo). Extending our methodology to social networks that sort stories algorithmically (e.g., Facebook) is a natural next step. Currently, RedQueen optimizes a quadratic loss on the position of a broadcaster’s most recent post on her followers’ feeds over time. However, it would be useful to derive optimal broadcasting intensities for other losses, e.g., time at the top. Moreover, we assume that only one broadcaster is using RedQueen. A very interesting follow-up would be augmenting our framework to consider multiple broadcasters under cooperative, competitive and adversarial environments. Finally, the novel technical aspects of our problem formulation, e.g., optimal control of jump SDEs with double stochastic temporal point processes, can be applied to other control problems in social and information networks such as activity shaping and opinion control .

References

Proof of Proposition 1

Using the left continuity of poisson processes, we have that:

Then, using Ito’s calculus , we can rewrite the differential in the second term as

Proof of Lemma 3

Proof of Lemma 4

According to the Stone-Weierstrass theorem, any continuous function in a closed interval can be approximated as closely as desired by a polynomial function . So by assuming the continuity of cost function we consider general form

where $m$ and $n$ are arbitrary large numbers. Indeed in each time $t$ we approximate a two variate function of $r(t)$ and $\lambda(t)$ by a polynomial where the coefficient are defined by the time varying functions $f_{ij}(t)$. If we substitute this function in to Eq. 13 and simplifying the expression we would have

where for notational simplicity we omitted the time argument of functions. To find the unknown functions $f_{ij}(t)$, we equate the coefficient of different variables. If we consider the coefficient of $r^{2n}$, we have $f_{n0}(t)=0$. We can continue this argument for $n-1,n-2,\cdots,2$ to show that $\forall i\geq 2;\,f_{i0}(t)=0$. Similar reasoning for coefficients of $r^{2i}\lambda^{2j}$ shows that $\forall j,i\geq 2;f_{ij}(t)=0$. Finally, the coefficient of $r^{2}$ is $1/2q-1/2\,s^{-1}f^{2}_{10}(t)=0$ so $f_{10}(t)=(sq)^{1/2}$. If we rename $f_{0j}(t)$ to $g_{j}(t)$ and $f_{00}(t)$ to $f(t)$, then we have

We can continue the previous method to find the remaining coefficients and completely define the cost-to-go function. If we equate the coefficient of $\lambda^{j}$ to zero we would have a system of first oder differential equation which its $j$’th row is

When $\lambda_{0}(t)=\lambda_{0}$, we can express this using matrix differential equation $\bm{g}^{\prime}(t)=A\bm{g}(t)$. and its solution is $\bm{g}(t)=c_{1}e^{\zeta_{1}t}\bm{u}_{1}+c_{2}e^{\zeta_{2}t}\bm{u}_{2}+\cdots+c_{n}e^{\zeta_{n}t}\bm{u}_{n}$ where $\zeta_{i}$ and $\bm{u}_{i}$ are eigenvalue and eigenvector of matrix $A$ and $c_{i}$ is a constant found using the terminal conditions. Since in triangular matrices diagonal entries are eigenvalues, we have $\bm{g}(t)=\sum_{j=1}^{m}c_{i}e^{j(\beta-\alpha)}\bm{u}_{i}$. We can approximate general time varying $\lambda_{0}(t)$ using piecewise function and repeat the above procedure for each piece.

Lemma 6

Let $x(t)$ and $y(t)$ be two jump-diffusion processes defined by following jump SDEs:

where $N(t)$, $M(t)$ are independent jump processes. If function $F(x,y,t)$ is once continuously differentiable in $x$, $y$ and $t$, then,

Proof According to the definition of differential,

where we used the complete notation for $F$ to be more clear. Using the zero-one law of point processes, we can write

where for notational simplicity we drop arguments of all functions except $F$. Then, we can expand the first three terms in the right hand sides:

using that the bilinear differential form $dt\,dN(t)=0$ and $dN(t)dM(t)=0$ by the zero-one jump law . Finally