-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathindex.html
465 lines (391 loc) · 20.8 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>RedQueen Demo</title>
<!-- MathJax configuration must come before MathJAX is loaded even if async -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
TeX: {
extensions: [ "color.js" ]
}
});
</script>
<script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_SVG" async></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/fetch/2.0.1/fetch.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.4.0/d3.min.js"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pure/0.6.2/buttons.css">
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css">
<link rel="stylesheet" href="css/tufte.css">
<link rel="stylesheet" href="css/main.css">
<link rel="favicon" href="favicon.ico">
</head>
<body>
<article>
<div style="display: none">
$$
\definecolor{us}{RGB}{239, 168, 86}
\definecolor{other}{RGB}{74, 179, 193}
$$
</div>
<img src="img/red_queen.512.png" alt="RedQueen"
aria="hidden" class="red-queen-icon" />
<h1 class="red-queen">
RedQueen
</h1>
<p class="subtitle">
An Online Algorithm for Smart Broadcasting in Social Networks
</p>
<ul class="subtitle">
<li>Presented at <a href="http://www.wsdm-conference.org/2017/">WSDM, 2017</a>;</li>
<li>Full paper at <a href="https://arxiv.org/abs/1610.05773">arxiv.org/abs/1610.05773</a>;</li>
<li>Source code at <a href="https://github.com/Networks-Learning/RedQueen"><i class="fa fa-github"></i>Networks-Learning/RedQueen</a></li>
</ul>
<section>
<h2>Introduction</h2>
<p>
User attention is becoming a sparse commodity. This is evinced by the
proliferation of studies which point to information overload or to the
plethora of articles proclaiming to recommend when to post your messages
to maximise the probability of your followers reacting to the post.
<!-- Can give references here -->
</p>
<p>
We will look at <span class="us">a broadcaster</span> who wants his
posts to gain more attention on the feed of one follower and see how he
can regulate his posting to do that.
</p>
<h2>Feeds in social media</h2>
<p>
Feeds in social media display posts of all <em>followees</em> of the
user (the follower) in some order. However, the follower does not pay
equal attention to all posts. Instead, more attention is given to the
posts on top of the feed while the posts which disappear <em>underneath
the fold</em> are given little attention.
<label class="margin-toggle sidenote-number" for="sn-overload-citation"></label>
<input id="sn-overload-citation" class="margin-toggle" type="checkbox">
<span class="sidenote">
See <a href="http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0098914">Leveraging Position Bias to Improve Peer Recommendation</a>, <a href="https://arxiv.org/abs/1605.02660">Information is not a Virus, and Other Consequences of Human Cognitive Limits</a>, <a href="https://people.mpi-sws.org/~manuelgr/pubs/efficiency-wsdm16.pdf">On the Efficiency of the Information Networks in Social Media</a>
</span>
</p>
<p>
Let us define the rank \( r(t) \) as the position of the <em>first</em>
post by the broadcaster on the follower's feed. It is a measure of
visibility of the broadcasters post. One way of seeking the follower's
attention is to minimize the rank \( r(t) \).
</p>
<figure>
<label class="margin-toggle" for="feed-figure">⊕</label>
<input id="feed-figure" class="margin-toggle" type="checkbox">
<span class="marginnote">
Feed of a follower contains posts broadcast by several sources,
including <span class="us">our broadcaster</span>, i.e. the source
we are interested in helping to remain at the top.
</span>
<img src="img/when-to-post-problem-demo.svg" alt="When to post problem" class="full-width">
</figure>
<!--
<label class="margin-toggle" for="fig-redqueen">⊕</label>
<input id="fig-redqueen" class="margin-toggle" type="checkbox">
<span class="marginnote">
<svg viewBox="0 0 100 150" id="example-feed" class="margin content"></svg>
A bursty feed of a follower with the rank of the users.
</span>
-->
<p>
In order to minimize the rank, we first need to understand how it evolves.
If the feeds are sorted by the time of the post, with most recent posts appearing on top, then the dynamics of the rank \( r(t) \) of the <span class="us">broadcaster</span> in the feed can be modeled using the following equation:
<label class="margin-toggle" for="generalize-rank-algo">⊕</label>
<input id="generalize-rank-algo" class="margin-toggle" type="checkbox">
$$
r(t+dt) = \left\{
\begin{array}{ccccl}
& (r(t)+1) & {\color{other} dM(t)} & {\color{us} (1-dN(t))} & {\color{other} \text{Others post}}\\
+ & 0 & {\color{other}(1 - dM(t))} & {\color{us} dN(t)} & {\color{us} \text{Our broadcaster posts}}\\
+ & r(t) & {\color{other} (1 - dM(t))} & {\color{us} (1- dN(t))} & \text{No-one posts}
\end{array}
\right.
$$
where \( {\color{other} dM(t)}, {\color{us} dN(t)} \in \{0, 1\} \) denote the presence or absence of a
<em>broadcast</em> in the respective point process at time \( t \).
<span class="marginnote">
Our method can generalize to any ordering of
posts as long as we can reverse-engineer the algorithm and write out
the dynamics of \( r(t) \).
</span>
</p>
<p>
The evolution of \( \color{us} N(t) \) is under the control of <span class="us">the broadcaster</span>,
whereas the \( \color{other} M(t) \) may behave in various ways:
</p>
<ul>
<li>It may be nearly constant (e.g. large number of diverse followees)</li>
<li>It may have bursts (e.g. breaking news posts)</li>
<li>It may be piecewise constant with some period (e.g. most followees
are from a particular time zones)</li>
<li>\( \ldots \)</li>
</ul>
<p>
<label class="margin-toggle" for="karimi-assumption">⊕</label>
<input id="karimi-assumption" class="margin-toggle" type="checkbox">
<span class="marginnote">
<a href="http://www.kdd.org/kdd2016/subtopic/view/smart-broadcasting-do-you-want-to-be-seen">
Karimi et. al.
</a> assume that the broadcasting frequency of
<span class="other">other broadcasters</span> is piecewise constant.
</span>
Thanks to our novel formulation of the problem, our solution
<span class="red-queen">RedQueen</span> is able to handle all of these
cases, <em>without needing to perform any model inference using historical data for \( \color{other} M(t) \)</em>.
</p>
<h2>Methodology</h2>
<p>
Given the dynamics of the rank and of <span class="others">other broadcasters</span>,
as stochastic jump differential equations, we can attempt to find the optimal rate
of posting for <span class="us">the broadcaster</span> \( u(t) \) by formulating it
as a variable in an <a href="https://en.wikipedia.org/wiki/Hamilton%E2%80%93Jacobi%E2%80%93Bellman_equation#Extension_to_stochastic_problems">stochastic control problem</a>.
However, before that, we have to choose a loss function which we will
aim to optimize for.
</p>
<p>
We choose the following loss function:
<label class="margin-toggle" for="generalize-multiple-followers">⊕</label>
<input id="generalize-multiple-followers" class="margin-toggle" type="checkbox">
<span class="marginnote">
This objective can be generalized for multiple followers. For details,
see <a href="https://arxiv.org/abs/1610.05773">our paper</a>.
</span>
<!--
$$
\begin{align}
\underset{u(t_0, t_f]}{\text{minimize}} &
\quad \mathbb{E}_{(N, M)(t_0, t_f]}\left[
\phi(r(t_f)) + \int_{t_0}^{t_f} \ell(r(\tau), u(\tau)) d\tau
\right] \\
\text{subject to} & \quad u(t) \geq 0 \quad \forall t \in (t_0, t_f]
\end{align}
$$
<span class="marginnote">
This is a common way to formulate problems for <a href="https://en.wikipedia.org/wiki/Hamilton%E2%80%93Jacobi%E2%80%93Bellman_equation#Extension_to_stochastic_problems">solving stochastic control problems</a>.
</span>
-->
$$
\begin{align}
\underset{u(t_0, t_f]}{\text{minimize}} &
\quad \mathbb{E}_{({\color{us} N}, {\color{other} M})(t_0, t_f]}\left[
\int_{t_0}^{t_f} \left( \frac{1}{2} s \,r^2(\tau) + \frac{1}{2} q\,u^2(\tau) \right) d\tau
\right] \\
\text{subject to} & \quad u(t) \geq 0 \quad \forall t \in (t_0, t_f]
\end{align}
$$
</p>
<p>
<label class="margin-toggle" for="karimi-loss">⊕</label>
<input id="karimi-loss" class="margin-toggle" type="checkbox">
<span class="marginnote">
Karimi et. al. optimize for <em>Time spent in top-k</em>, wherein, they find the
rates which maximize the time the broadcaster's posts spend with \( r(t) \lt k \).
In <a href="https://arxiv.org/abs/1610.05773">our paper</a>, we show
that our approach, though optimizing for a different loss function,
still outperforms the offline method.
</span>
This function penalizes high ranks \( \frac{1}{2} s \,r^2(t) \)
as well as posting with high frequency \( \frac{1}{2} q\,u^2(t) \), with
tunable weights \( s \) and \( q \) to trade off between them.
</p>
<p>
We integrate the this loss function over the desired interval
\( [ t_0, t_j ] \) and, since the future is stochastic, we attempt
to find the posting rate \( u(t) \) of <span class="us">the broadcaster</span>
which minimizes the expectation of the integral.
</p>
<!--
<p>
The \( s \) and the \( q \) denote the relative penalty of
the rank we obtain and the amount of broadcasting we do.
<label class="margin-toggle" for="generalize-significance">⊕</label>
<input id="generalize-significance" class="margin-toggle" type="checkbox">
<span class="marginnote">The term \( s \) can be made a function of time, i.e. \( s(t) \), to
change the <em>significance</em> of obtaining a high rank at time \( t \).
Also, in case of multiple followers, the term \( s \) can be a vector, which can be used
to weigh the ranks of the broadcaster on different follower's feeds differently.
For details, see <a href="https://arxiv.org/abs/1610.05773">our paper</a>.
</span>
</p>
-->
<p>
With this choice of the loss function, the optimization problem can be solved analytically by formulating the optimal cost-to-go, deriving a PDE using the <a href="https://en.wikipedia.org/w/index.php?title=Hamilton%E2%80%93Jacobi%E2%80%93Bellman_equation&wteswitched=1">Hamilton-Jacobi-Bellman equation</a> and then solving it.
</p>
<p>
Finally, on solving the PDE, we arrive at the following elegant solution:
$$
\overbrace{u(t)}^{\text{broadcast intensity}} = \sqrt{s/q}\,\underbrace{r(t)}_{\text{Rank in feed}}
$$
</p>
<p>
This function states that the rate at which <span class="us">the broadcaster</span> must post messages (i.e. the <em>urgency</em> of posting), should be proportional to how <em>bad</em> his rank \( r(t) \) is.
Hence, he will have to post <em>faster</em> to stay where he originally was (i.e. at the top).
</p>
<p>
Determining the rate requires only knowing the rank of
<span class="us">the broadcaster</span> on the feed(s) of his follower(s).
This information can be calculated in \( \mathcal{O}(1) \) time, given
the stream of posts from <span class="other">other broadcasters</span>,
the sampling, as shown <a href="#sampling">below</a>, too takes only
\( \mathcal{O}(1) \) time, making this an efficient online algorithm
for determining when-to-post.
</p>
<h2 id="sampling">From <em>rate-of-posting</em> to <em>when-to-post</em></h2>
<p>
<!--
<label class="margin-toggle" for="eqn-user-rate">⊕</label>
<input id="eqn-user-rate" class="margin-toggle" type="checkbox">
<span class="marginnote">
</span>
-->
Now that we know how <span class="us">the broadcaster</span> should
regulate his messages, we have to determine when exactly should the next post be made.
</p>
<p>First, notice that \( u(t) \) changes only when \( r(t) \) changes and in steps of size \( \sqrt{{s}/{q}} \).</p>
<p>
Thanks to the superposition property of Poisson point processes
we can treat each <em>jump</em> in \( u(t) \) as the start of a new Poisson process.
</p>
<figure>
<label class="margin-toggle" for="superposition">⊕</label>
<input id="superposition" class="margin-toggle" type="checkbox">
<span class="marginnote">
The process \( u(t) \) can be seen as a super-position of multiple
Poisson processes starting at the times the rank \( r(t) \) changes,
i.e. when <span class="other">other broadcasters</span> post
messages.
</span>
<img src="img/superposition.svg"
alt="u(t) is superposition of multiple point processes"
class="centered width-75">
</figure>
<p>
Now to draw the time of first event for \( u(t) \), i.e. when
<span class="us">our broadcaster</span> posts, we can draw samples
from all point processes and take the minimum.
</p>
<figure>
<label class="margin-toggle" for="sampling-note">⊕</label>
<input id="sampling-note" class="margin-toggle" type="checkbox">
<span class="marginnote">
Since \( u(t) \) is a sum of several independent Poisson processes,
the first event which occurs according to it is the earliest of the
first events of each of its components.
</span>
<img src="img/sampling.svg"
alt="sampling u(t) involves taking the minimum of all samples for individual processes"
class="centered width-75">
</figure>
<p>
Since drawing one sample is an \( \mathcal{O}(1) \) operation, and we
draw one sample each time <span class="other">other broadcasters</span>
post, we only have to take \( \mathcal{O}(M(t_f)) \) samples.
</p>
<h2>Demo</h2>
<p>Choose the metric you would like to see and press the <code>Play</code> button to start the demo.</p>
<p class="metric-control">
<span class="js-option option">
<input id="avg_rank" type="radio" name="performance_metric" value="avg_rank" checked class="js-perf-metric">
<label for="avg_rank">Rank \( r(t) \)</label>
</span>
<span class="js-option option">
<input id="time_at_top" type="radio" name="performance_metric" value="time_at_top" class="js-perf-metric">
<label for="time_at_top">Time at top \( \int_{0}^{t} \mathbb{I}(r(\tau) \lt 1)\, d\tau \)</label>
</span>
</p>
<p class="pure-button-group centered sans" role="group" aria-label="interactive buttons">
<button class="small pure-button button-play js-play">
<i class="fa fa-play"></i> Play
</button>
<button class="small pure-button button-stop js-stop">
<i class="fa fa-stop"></i> Stop
</button>
</p>
<figure>
<label class="margin-toggle" for="redqueen-demo-caption">⊕</label>
<input id="redqueen-demo-caption" class="margin-toggle" type="checkbox">
<span class="marginnote">
Interactive demo showing the performance (i.e. \( r(t) \)) of
<span class="red-queen">RedQueen</span> against a Poisson broadcaster
(who posts at random times) against a bursty stream of tweets coming
from other broadcasters.
</span>
<div class="long vis-aspect">
<svg id="perf-1-vis" width="100%" class="content" viewBox="0 0 300 100"></svg>
</div>
<div class="long vis-aspect">
<svg id="perf-2-vis" width="100%" class="content" viewBox="0 0 300 100"></svg>
</div>
<div class="equal-size">
<div class="tall left vis-aspect">
<svg class="content" id="feed-1-vis" viewBox="0 0 100 150"></svg>
</div>
<div class="tall right vis-aspect">
<svg id="feed-2-vis" class="content" viewBox="0 0 100 150"></svg>
</div>
</div>
</figure>
<h2>More details</h2>
<p>
<a href="https://arxiv.org/abs/1610.05773">Our paper</a> contains a mathematical description of <span class="red-queen">RedQueen</span>,
and several extensions including, but not limited to:
</p>
<ul>
<li>Comparison against an Oracle and the state of the art and saw that our algorithm fared favourably.</li>
<li>Extension to handle multiple users and to handle time varying weights for followers.</li>
<li>Testing under <em>truthful what-if</em> conditions by playing back tweets on falls of followers of over 2000 Twitter users. <span class="red-queen">RedQueen</span> was able to obtain better average rank as well as higher time in the top-1 compared to the real users as well as against the current state of the art. </li>
</ul>
<h2>The Name <em class="red-queen">RedQueen</em></h2>
<p>
The name is taken from the <a href="https://en.wikipedia.org/wiki/Red_Queen">Red Queen's race</a>
incident in <a href="https://en.wikipedia.org/wiki/Lewis_Carroll">Lewis Carroll</a>'s
book <a href="https://en.wikipedia.org/wiki/Through_the_Looking-Glass">Through the Looking Glass</a>.
In particular, the Queen's quote:
</p>
<div class="epigraph">
<blockquote>
"Now, here, you see, it takes all the running you can do, to keep in the same place."
<footer>Red Queen</footer>
</blockquote>
</div>
<h2>Authors</h2>
<p>
The webpage was created by <a href="https://musicallyut.in">Utkarsh Upadhyay</a>.
The other authors of <span class="red-queen">RedQueen</span> are <a href="https://azarezade.github.io/">Ali Zarezade</a>, <a href="http://sharif.edu/~rabiee/">Hamid R. Rabiee</a>, and <a href="https://people.mpi-sws.org/~manuelgr/">Manuel Gomez-Rodriguez</a>.
</p>
</section>
<hr>
<section class="small-font">
<h3>Acknowledgements</h3>
<p>
The <em class="red-queen">RedQueen</em> icon was made by <a href="http://www.flaticon.com/authors/zlatko-najdenovski" title="Zlatko Najdenovski">Zlatko Najdenovski</a> from <a href="http://www.flaticon.com" title="Flaticon">www.flaticon.com</a>. It is licensed by <a href="http://creativecommons.org/licenses/by/3.0/" title="Creative Commons BY 3.0" target="_blank">CC 3.0 BY</a>.
<!-- Other icons made by <a href="http://www.freepik.com" title="Freepik">Freepik</a> from <a href="http://www.flaticon.com" title="Flaticon">www.flaticon.com</a> are licensed by <a href="http://creativecommons.org/licenses/by/3.0/" title="Creative Commons BY 3.0" target="_blank">CC 3.0 BY</a></div> -->
</p>
</section>
<section>
<h3>Source code</h3>
<ul>
<li><a href="https://github.com/Networks-Learning/RedQueen"><i class="fa fa-github"></i>Networks-Learning/RedQueen</a></li>
<li><a href="https://github.com/Networks-Learning/RedQueen-website"><i class="fa fa-github"></i>Networks-Learning/RedQueen-website</a></li>
</ul>
</section>
<a href="https://imprint.mpi-klsb.mpg.de/sws/learning.mpi-sws.org/redqueen/">Imprint</a> / <a href="https://data-protection.mpi-klsb.mpg.de/sws/learning.mpi-sws.org/redqueen">Data Protection</a>
</article>
<script src="js/main.js"></script>
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-8158678-1");
pageTracker._trackPageview();
} catch(err) {}
</script>
</body>
</html>