hide
Free keywords:
Statistics, Machine Learning, stat.ML,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG,cs.SI
Abstract:
User engagement in social networks depends critically on the number of online
actions their users take in the network. Can we design an algorithm that finds
when to incentivize users to take actions to maximize the overall activity in a
social network? In this paper, we model the number of online actions over time
using multidimensional Hawkes processes, derive an alternate representation of
these processes based on stochastic differential equations (SDEs) with jumps
and, exploiting this alternate representation, address the above question from
the perspective of stochastic optimal control of SDEs with jumps. We find that
the optimal level of incentivized actions depends linearly on the current level
of overall actions. Moreover, the coefficients of this linear relationship can
be found by solving a matrix Riccati differential equation, which can be solved
efficiently, and a first order differential equation, which has a closed form
solution. As a result, we are able to design an efficient online algorithm,
Cheshire, to sample the optimal times of the users' incentivized actions.
Experiments on both synthetic and real data gathered from Twitter show that our
algorithm is able to consistently maximize the number of online actions more
effectively than the state of the art.