Network Clocks: Detecting the Temporal Scale of
Information Diffusion
Daniel J. DiTursi∗†

Gregorios A. Katsios∗

∗ Department

arXiv:1709.04015v1 [cs.SI] 12 Sep 2017

of Computer Science
State University of New York at Albany
Albany, NY 12222

Abstract—Information diffusion models typically assume a
discrete timeline in which an information token spreads in the
network. Since users in real-world networks vary significantly in
their intensity and periods of activity, our objective in this work
is to answer: How to determine a temporal scale that best agrees
with the observed information propagation within a network?
A key limitation of existing approaches is that they aggregate
the timeline into fixed-size windows, which may not fit all network
nodes’ activity periods. We propose the notion of a heterogeneous
network clock: a mapping of events to discrete timestamps that
best explains their occurrence according to a given cascade
propagation model. We focus on the widely-adopted independent
cascade (IC) model and formalize the optimal clock as the one
that maximizes the likelihood of all observed cascades. The single
optimal clock (OC) problem can be solved exactly in polynomial
time. However, we prove that learning multiple optimal clocks
(kOC), corresponding to temporal patterns of groups of network
nodes, is NP-hard. We propose scalable solutions that run in
almost linear time in the total number of cascade activations
and discuss approximation guarantees for each variant. Our
algorithms and their detected clocks enable improved cascade
size classification (up to 8% F1 lift) and improved missing cascade
data inference (0.15 better recall). We also demonstrate that the
network clocks exhibit consistency within the type of content
diffusing in the network and are robust with respect to the
propagation probability parameters of the IC model.

I. I NTRODUCTION
Models for information propagation in social networks
assume a discrete timeline over which the information
spreads [8, 9]. At the same time, real-world network data
is collected at different temporal resolutions e.g. minutes,
hours, weeks. Hence, a common step before analyzing realworld data is to define a temporal scale to aggregate events in
the network into discrete snapshots. Such aggregations make
the implicit assumption that there exists a single temporal
resolution that works well for all network nodes and periods of
activity. Empirical studies of social network activity, however,
demonstrate a wide variance in activity levels across users
and across time [13, 18, 19], thus challenging the above
assumption. How can we account for heterogeneity in user
activity over time when analyzing information propagation
data from real-world networks?
To address the above problem, we propose the problem of
detecting data-driven heterogeneous temporal aggregations for
information diffusion under the widely-adopted independent
cascade (IC) model [8, 7]. We formalize the problem as finding
the temporal aggregation that maximizes the likelihood of

Petko Bogdanov∗

† Department

of Computer Science
Siena College
Loudonville, NY 12211

1

3

0

4

2
6

5

X (1)
∆1 = h1, 1ih2, 5ih6, 6i
LL(∆1 ) = −13.9
X (2)
∆2 = h1, 2ih3, 4ih5, 6i
LL(∆1 ) = −16.3

1
6

2

3

4

5
5

6
0

2
0

3
1

4

2

∆1,2 = h1, 1ih2, 2ih3, 6i
LL(∆1,2 ) = −34.6

Fig. 1. An example network and two cascades X (1) and X (2) with their
original measured activation times between 1 and 6. Assuming an independent
cascade with spontaneous activation probability pe = 0.001 and a neighbor
propagation probability pn = 0.1, the best clock for X (1) is ∆1 with a
log-likelihood LL = −13.9 and the best clock for X (2) is ∆2 with LL =
−16.3. An optimal clock that maximizes the likelihood of both cascades is
∆1,2 , which is suboptimal for the individual cascades.

observed cascades according to the IC model. We allow this
aggregation to vary across time and across users, driven by
the likelihood of observed data. We refer to such an optimal
temporal aggregation as a network clock: a discrete timeline
with time steps determined by user activity as opposed to
regular intervals of “wall-clock” time.
The example in Fig. 1 involves a small graph of 7 nodes
(left) and two cascades X 1 and X 2 (right), which are observed
over the duration of 6 discrete time steps. A cascade is a
sequence of activation events with their originally measured
times define the original time resolution of observed cascades.
On the right, cascades are presented as directed graphs where
edges denote the possibility of influence from an activated
node to a network neighbor which is activated at a later time
(the horizontal position of nodes corresponds to their original
time of activation). Using the original time resolution for
cascade X 1 will render nodes 5 and 0 being as spontaneous
activations, since IC requires that potential influence nodes are
activated in the immediately preceding time step. Such view
of time will result in a low IC likelihood as activations through
the network have typically higher-likelihood. Thus, using the
original time resolution as a network clock will poorly capture
how nodes influenced each other.
Alternatively, the clock ∆1 aggregates the middle 4 time
ticks into a single time step, i.e. the activations of nodes 2
and 5 are treated as simultaneous, with the activation of 6
preceding them and that of 0 immediately following. As all
activations except the first are now explained by the immediately prior influence of a neighbor, this clock maximizes the

likelihood of the observed activations being produced by an
IC process.
In our running example (Fig. 1), the clocks ∆1 and ∆2 that
optimize the two cascades separately are both different from
each other and from the clock that maximizes the likelihood
of both cascades considered together (∆1,2 ). Imposing the
same overall clock on all users and all cascade instances
may be overly restrictive. Different users might engage in the
information propagation at different times depending on their
interest, overall activity, time zone, etc. In addition, different
information, e.g. videos vs. text, may spread at different rates
and at different times. Hence, we also consider the problem
of finding multiple clocks for a single dataset.
Knowledge of the network clocks can improve a variety of
applications. Based on past propagation, one can predict likely
times of future activity and allocate computational resources
to handle the user traffic accordingly. In addition, clocks may
enable classification of cascades future sizes [6] and the type
of non-text information (e.g. video and photos) without deep
content analysis, but instead by relying on similarities to other
annotated content. The latter may unlock applications such
as automated hash-tagging for improved social media stream
access. Given knowledge of community-specific clocks, one
can also impute missing activations [20, 14], which in turn
can be used for better influence maximization in the face of
a deadline (e.g. elections or ticket sales), and the improved
quality of simulations of diffusion processes.
Our contributions in this work are as follows:
1. We introduce the novel concept of heterogeneous network
clocks: optimal temporal aggregations for observed information diffusion in social media. We show that while the single
network clock (OC) problem can be solved polynomially, the
multiple network clocks (kOC) problem is NP-hard.
2. We provide an exact solution for OC that, while polynomial, is impractical for non-trivial instances. We also propose
fast solutions for both OC and kOC, capable of processing
instances with millions of nodes and cascade activations.
3. We demonstrate the utility of the network clocks for
multiple applications, boosting the performance of existing
algorithms for cascade size prediction (increase in F1 -measure
by 8%) and cascade completion (improving recall by 0.2 or
more) in both synthetic and real-world data.
II. P ROBLEM FORMULATION AND COMPLEXITY
A. Preliminaries
We denote a static directed network as G(V, E) with nodes
V and edges E ⊆ V × V . We refer to individual instances
of diffusion processes over time through this network as
cascades. Thus, a cascade Xi = {(u, t)} is a set of nodetime pairs, each representing the activation of node u at time
t, where the set of all observed cascades in a data set is
X = {X1 , . . . , Xm }. We assume a discrete timeline where
1 and T are the times of the first and last activation events in
X, respectively. We also assume that each cascade activates a
vertex at most once.
Among the multiple models for cascade processes, we focus
on the well-studied independent cascade (IC) model initially

introduced by Goldenberg et al. [8]. The key intuition behind
the model is that, with respect to a given cascade, each
node may be in only one of three states: inactive, active, or
previously activated. The critical notion in this model is that
nodes can only influence neighbors for a single time period
after activation. In other words, a node that is activated at
time t increases the likelihood that its neighbors activate at
time t + 1, but not at t + 2 or any later time.
The IC model has two key parameters: the probability pn
that a newly activated node activates any network neighbor,
and the probability pe that an inactive node “spontaneously”
activates due to external factors. Note that the above assumes
homogeneous activation probabilities for all nodes and neighbor links. Our methods are directly applicable to the nonhomogeneous IC setting where probabilities may differ across
nodes and edges, but we do not explore that setting here. We
assume that pe is much smaller than pn ; otherwise the network
structure becomes much less important. As suggested by the
name of the model, all activation events are presumed to be
independent of each other.
The set of incoming neighbors of u is denoted by N (u) =
{v | (v, u) ∈ E}; these are the nodes that can potentially
influence u. The set of nodes activated as part of a cascade
X at time t is denoted by A(X, t). The activation time of
node v within cascade X is denoted as X(v). Finally, the
set of newly active neighbors of v at time t are denoted as
C(X, v, t) = A(X, t − 1) ∩ N (v), i.e. those are the nodes
that can potentially activate v at time t.
Given the above definitions, we can quantify the a priori
likelihood that node v is part of cascade X at time t as follows:
(
1, if X(v) < t i.e. v is already in X
L(v, X, t) =
(1)
1 − (1 − pe )(1 − pn )|C(X,v,t)| , o/w.
This likelihood reflects the possibility of a node being activated
by at least one contagious neighbor or by sources external
to the network. In order to characterize the likelihood of
all independent observations, we use the common practice
of working with log-likelihoods. Thus, the log-likelihood of
node v joining X at time t is LL(X, v, t) = log L(X, v, t).
For convenience, we also define the log likelihood of v not
joining X at time t as LL(X, v, t) = log 1 − L(X, v, t). We
can now quantify the log-likelihood of all observed cascades
X and their activation events as:
T
XX
X
X

LL(X) =
LL(u, X, t) +
LL(v, X, t)
X∈X t=1 u∈A(X,t)

v ∈A(X,t)
/

(2)
Note that the independence assumption across cascades and
activation events results in the above sum of log-likelihoods.
B. Network clocks and likelihood improvement
The independent cascade model assumes discrete time of
events and that all nodes are participants in the diffusion
process at every time step. Such assumption enforces a uniform mapping of “wall-clock” time to network events across
the entire network, and thus, renders IC models infeasible to

interpret information diffusion in real-world networks, which
are often not governed by a single clock.
For example, consider an online social network user who
checks her feed upon waking up, once or twice during lunch
break, and several times in the evening. No uniform timeline
can explain her activity sessions well - short time steps will
make morning activity appear unrelated to posts that came in
overnight, while long time steps may lose information about
rapid responses that occur in the evening. A heterogeneous
division of the timeline, which we term a network clock is
needed to accurately explain such activity.
A network clock ∆ is a partitioning of T into contiguous
segments of the original timeline corresponding to “new”
discrete time steps. In effect, the events that occur within
each interval of the timeline are considered to be simultaneous.
In the example from Fig. 1, the clock ∆1 for cascade X (1)
partitions the time into intervals h1, 1i, h2, 5i and h6, 6i, which
renders the activations of nodes 2 and 5 simultaneous.
Formally, a network clock ∆ = {δ1 , . . . , δf } is a set of
adjacent non-overlapping time intervals δi = hts , te i that span
the original timeline T, i.e. :
ts (δi ) ≤ te (δi ), ts (δi ) = te (δi−1 ) + 1, ∀i.
The two extreme clocks are the maximum aggregation (i.e.
all original timestamps are simultaneous): ∆max = {h1, T i},
and the minimum aggregation, corresponding to the original
timeline: ∆min = {h1, 1i, . . . , hT, T i}. The total number of
possible clocks is 2T −1 , since we can either split or not
between any two consecutive points in h1, T i.
For a fixed clock ∆, we treat δi as individual consecutive
time steps (indexed by i); however, as necessary we also
use δ∆ (t) to denote the unique interval δ ∈ ∆ containing
the original time t. Given a clock ∆, the set of active
nodes at period δ is all activations that happened during δ,
Ste (δ)
denoted A(X, δ) = t=t
A(X, t); other temporal entities
s (δ)
are similarly mapped from the original times t to periods δ. We
can now redefine the clock likelihood of an observed activation
during interval δi following interval δi−1 as:
(
1, when X(v) < ts (δi )
L(v, X, δi ← δi−1 ) =
1 − (1 − pe )(1 − pn )|C(X,v,δi )| , o/w.
(3)
Note that the set of contagious neighbors of v at time δi are
determined by the preceding interval: C(X, v, δi ) = N (v) ∩
A(X, δi−1 ). As a result, different clocks will result in different
likelihoods of observed events. We denote the log-likelihood
of all events given a clock as LL(X|∆), defined analogously
to Eq. 2, where the sum over t and selection of active nodes
is replaced by a sum over clock intervals.
Our goal is to find a clock (if any) that provides a better
explanation of observed cascades X than the timeline of ∆max ,
a default clock that groups all events into a single step. A clock
improvement I(X|∆) is the increase in likelihood compared
to that of the default clock:
I(X|∆) = LL(X|∆) − LL(X|∆max ).

In our example in Fig. 1 the default clock ∆max will
render the activation of all nodes spontaneous (i.e. activated
from external sources) due to the lack of preceding time
steps, and thus, of contagious neighbors. The log-likelihood
of cascade X (1) (in red) under the default clock ∆max is
L(X (1) |∆min ) = −23.5, while the same quantity for clock
∆1 is L(X (1) |∆1 ) = −13.9, hence the improvement of ∆1
for cascade X (1) is I(X (1) |∆1 ) = 9.6. Similarly, the improvement of the clock ∆1,2 when both cascades are considered
simultaneously can be calculated as I({X (1) , X (1) }|∆1,2 ) =
−34.6 − (−40) = 5.4.
C. Optimal network clock problems: OC and kOC
We are now ready to define our clock optimization problems: the Optimal clock problem (OC) which seeks to identify
a temporal clock that best explains all observed cascades; and
the k-Optimal Clock problem (kOC) which maps nodes in the
network to one of k ≤ |V | clocks corresponding to different
temporal behaviors of network users. We show that the former
can be solved in polynomial time, while the latter is NP-hard.
Definition 1. [Optimal clock problem (OC)] Given a network G, a set of cascade observations X, and probabilities pe
and pn , find the clock ∆∗ = argmax∆ I(X|∆).
Problem OC asks for the single partition of time that best
captures the temporal properties of all observed cascades X
given the IC model. The problem is most applicable in cases
where either all of the network nodes have similar temporal
habits of social network interactions (e.g. 9am-5pm office
workers), or when cascades progress in a similar fashion.
In such cases it is desirable to detect this shared temporal
behavior across the whole network.
Unlike a homogeneous clock, the optimal solution of OC
will adaptively segment time in order to increase the likelihood
of observed data. Thus, periods of bursty activity may be
partitioned into more steps, while those of relatively low
activity combined into a single step. The number of potential
clocks is 2T −1 ; nevertheless, OC admits a polynomial-time
exact solution based on dynamic programming discussed in
detail in the following section.
The assumption of a single temporal clock shared among
all network nodes might be too stringent considering the size,
scope and heterogeneity of real-world OSN users. Beyond
9am-5pm office worker activity patterns, we might observe
those of high-school or college students, stay-at-home parents
or seniors and in addition all these diverse demographics may
reside in different time zones, while still participating in the
same global OSN. To account for such diverse population of
users we also consider a multiple clock version of the problem,
where each node “follows” a single clock.
One can think of a clock as how the events are temporally
perceived from the viewpoint of a node. Instead of imposing
the same clock on all nodes, we can model different behavioral patterns as multiple clocks that individual nodes follow.

where X(v) denotes the activations of node v in all cascades
in X. Note that I(X|D) can be evaluated in polynomial time if
the set of clocks D is predefined by calculating the likelihood
of each node v’s activations according to each clock.
In our example in Fig. 1 clock ∆1,2 is the best single
clock when considering both cascades X = {X (1) , X (2) };
however, under this clock, the influence from 6 → 5 in X (1)
is discounted since 6 is activated in the first interval of ∆1,2 ,
while 5 is activated in its third interval. Similarly, the potential
influences from 1 → 3 and 3 → 4 in X (2) are discarded as
all of those activations are rendered simultaneous according to
∆1,2 . Consider, however, a second alternative clock for these
cascades ∆ = h1, 3ih4, 4ih5, 6i. The improvement of both
clocks will exceed that of ∆1,2 alone, i.e. I(X|∆1,2 , ∆) >
I(X|∆1,2 ), since the likelihoods of the activations of nodes 3
and 4 will increase by being reassigned to ∆, thus considering
all of their potential network activations.
Definition 2. [k-Optimal clock problem (kOC)] Given a
network G, a set of cascade observations X, probabilities pe
and pn , and a positive integer k > 0 find the set of clocks
D∗ = argmaxD I(X|D), s.t. |D| ≤ k.
For values of k = 1 or k ≥ |V |, kOC can be solved in
polynomial time. k = 1 is equivalent to the OC problem
and can be solved using dynamic programming as discussed
in the next section, and when the budget of clocks exceeds
the number of graph nodes, k ≥ |V |, we can find the single
best clock that optimizes the improvement of a given node’s
activations and then assign this clock to the node. However,
for general k < |V | we show that the problem is NP-hard by a
reduction from Graph coloring to a decision version of kOC.
Theorem 1. kOC is NP-hard.
Proof. We show a reduction from k-Graph Vertex Coloring
(kVC) to a decision version of kOC. Given a graph, kVC asks
for a mapping of each node to at most k colors such that no
two colors are adjacent. Let kOC-B be a decision version of
kOC asking if there exist k clocks s.t. I(X|D) > B, B > 0. To
construct the reduction we will need to show how we obtain
an instance kOC from an instance of kVC and also set the
values of B and k.
Given a kVC instance G(V, E) we create an instance of
kOC involving a graph G0 (V 0 , E 0 ) with |V | + 2|E| nodes,
4|E| edges and 4|E| cascades using the gadget in Fig. 2. For
every kVC edge (u, v), we create four cascades involving two
activations each. The later activations of each of the cascades
involve nodes corresponding to the nodes in the kVC instance,
while the earlier activations involve unique other nodes. For
example, the gadget corresponding to edge (0, 1) in Fig. 2
involves the four cascades spanning times [1−4]. Two cascades
“end” with the equivalent node to 0 in kOC: (a01 , t1 ) → (0, t2 )
and (b01 , t3 ) → (0, t4 ); and another two with the equivalent

∆1
∆2

t: 1
kOC

v∈V

∆∈D

∆1
∆03

a01

∆03

∆2

∆03

∆1

∆2

∆03

∆2

∆03

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

0

b01

0

b02

2

b23

1

b12

1

0

a02

0

a23

2

a12

c01

1

c02

2

c23

3

c12

2

d01

1

d02

2

d23

3

d12

2

2

3

kVC

Given a set of clocks D = {∆1 , ∆2 ..., ∆k }, we define their
improvement as:


X
I(X|D) =
max LL(X(v)|∆) − LL(X(v)|∆min ) , (4)

0
1

Fig. 2.

Gadget used in the reduction from Vertex Coloring (kVC) to kOC.

of node 1: (c01 , t1 ) → (1, t4 ) and (d01 , t1 ) → (1, t4 ). Note
that it is not possible to devise a single clock that renders all
4 latter activations ((0, t2 ),(0, t4 ),and the two (1, t4 )) of the
cascades non-spontaneous, i.e. there is no set of splits in time
that will “cut” all 4 cascade activation edges exactly once.
Applying this transformation for each kVC edge we obtain
an instance of 4|E| cascades, where a pair of cascades coincides in time only if they are within the same gadget. We set
the log-likelihood requirement as B = 4|E| log pn , where we
set pe and pn such that log pe < 2|E| log pn . In other words,
we require k clocks that ensure that all latter gadget activations
are non-spontaneous.
If there exists a kVC solution, one can create a corresponding kOC solution by assigning one clock per color ensuring
that all activations of the corresponding nodes of that color
are non-simultaneous in each gadget. This is possible since
nodes of the same color will never appear in the same gadget.
Consider, as an example, the set of corresponding 4 clocks
for a 4-coloring of the kVC instance in Fig. 2. Alternatively,
assume there exists a kOC solution in which every cascade
activation edge is cut exactly once by the clock assigned to
the later node. Then all activations of a given end-node will
be rendered network-induced by at least one clock and we
can assign colors in the kVC instance based on this clock
assignment ensuring that colors will not be adjacent.
III. A LGORITHMS FOR OPTIMAL CLOCK DETECTION
Next we present our solutions for OC and kOC. We
first demonstrate that an exact solution for OC is possible
in polynomial time employing dynamic programming (DP).
Its complexity, however, makes it challenging to apply to
real-world instances; hence we propose a fast and accurate
greedy (GR) alternative. Although kOC is NP-hard, we show
that the improvement function is monotonic and submodular
with respect to the set of solution clocks, leading to greedy
generalizations GRDP and GR2 of our single clock solutions,
the former featuring an approximation guarantee. Tbl. I summarizes the algorithms and results discussed in this section.
A. Single-clock approaches
While there are O(2T −1 ) possible clocks for a timeline of
T original steps, we show that we can compute the optimal
one by considering O(T 2 ) intervals and employing dynamic
programming. Let S : {δse = hs, ei} be the set of all possible

Algorithm Problem Complexity Asymptotic Time Guarantee
DP
OC
Poly
O(|X|4 )
Exact
GR
OC
Poly
O(m|X| log(|X|))
GRDP
kOC
NP-hard
O(k|X|4 )
1 − 1/e
2
GR
kOC
NP-hard
O(km|X| log(|X|))
TABLE I
A LGORITHMS , COMPLEXITY AND APPROXIMATION GUARANTEES .

Algorithm 1 DP
Require: Graph G, set of cascades X
Ensure: Clock ∆∗ solution to OC
1: for e = 1 . . . T do
2:
I ∗ (δ1e , X) = I(δ1e ← ∅, X) = 0 // Init. intervals starting at t=1
3: end for
4: for s = 2 . . . T do
5:
for e = s . . . T do


6:
I ∗ (δse , X) = maxδ∈δs−1 I ∗ (δ, X) + I(δse ← δ, X)
←

sub-intervals of the timeline [1, T ], where 1 ≤ s ≤ e ≤ T
denote the start and end of the interval. Note that there is a
quadratic number of possible intervals |S| = T (T + 1)/2. Let
e
also δ←
denote the set of all intervals ending at e and starting
at a time no later than e. Let the improvement of v in cascade
X over interval δse given a preceding interval δbs−1 be:



← δbs−1 ) =
LL(v, X, δse ← δbs−1 )
LL(v, X, δse ← δbs−1 )



0

I(v, X, δse

− log pe

if X(v) > e
if X(v) ∈ δse
if X(v) < s,

(5)

where LL(v, X, δse ← δbs−1 ) is the interval log-likelihood of
v defined as in Eq. 3 with the set of active neighbors of v
C(X, v, δse ← δbs−1 ) = N (v) ∩ A(X, δbs−1 ). Note that in the
above definition we subtract the log-likelihood of the default
clock ∆min in case the activation of v is within the interval
X(v) ∈ δse to quantify the improvement due to v’s activation.
The total improvement of the interval transition δse is defined
as the sum of all node improvements in all cascades:
X X
I(δse ← δbs−1 , X) =
I(v, X, δse ← δbs−1 ). (6)
X∈X v∈V

We will denote with I ∗ (δse , X) the best improvement of loglikelihood up-to and including interval δse , over all sequences
of preceding intervals. In other words, I ∗ (δse , X) is the optimal
clock up to time e, such that the last interval in the clock is
δse . We can recursively define
h this quantity as:
i
I ∗ (δse , X) = max I ∗ (δ, X) + I(δse ← δ, X) .
s−1
δ∈δ←

(7)

The maximum in the definition is taken over the set of all
s−1
. Based on the
intervals ending immediately before δse : δ←
above definition, the improvement of the best clock is the
maximum over the best improvements of intervals ending at T ,
∗
i.e. I(X|∆∗ ) = argmaxδ∈δ←
T I (δ, X). This equivalence gives
us the blueprint for a dynamic programming (DP) solution that
progressively computes the improvement of all T (T + 1)/2
intervals and uses back-tracking to retrieve the optimal clock.
Alg. 1 presents the steps of the DP algorithm based on
Eq. 7 producing the optimal solution of OC. Steps 1-3 compute
the best improvement for the base cases of the recursion, i.e.
all intervals staring at t = 1 which do not have preceding
intervals. Since no nodes are active before this time, all
activations are considered spontaneous, and thus the individual
node improvement scores and the cumulative I(δ1e ← ∅, X) are
all zero. The nested loops in Steps 4-9 incrementally compute
the best improvement (Step 6) of intervals of increasing
starting position and record the preceding interval that leads to
the best improvement to be later used by backtracking (Step

7:
8:
9:
10:
11:
12:

bt(δse ) = δbs−1 , where δbs−1 is the maximizer in I ∗ (δse , X)
end for
end for
T
δb = argmaxδ∈δT I ∗ (δ, X) // Last interval of ∆∗
←
Reconstruct ∆∗ by recursively following bt() starting from bt(δbT )
∗
return ∆

Algorithm 2 GR
Require: Graph G, set of cascades X
Ensure: Clock ∆
1: ∆ = {h1, T i}
2: Ea = {(u, v, X)|(u, v) ∈ E, X(u) < X(v)} // Active edges
3: repeat
4:
C = ∅ // Set of independent cut positions
5:
for t in increasing activation times of all (u, t0 , X) ∈ X do
6:
Add active edges (u, v, X) to Ea (t) s.t. X(v) = t
7:
Compute I(Ea (t))
8:
if I(Ea (t)) > 0 then add-or-drop((t, Ea (t)) → C) end if
9:
Remove active edges (u, v, X) from Ea (t) s.t. X(u) = t
10:
end for
11:
if C 6= ∅ then Add all cuts C to ∆ end if
12: until C == ∅
13: return ∆

7). Note that at the time at which interval δse is considered,
the best improvement of all immediately preceding intervals
s−1
, X) is already available, thus allowing the recursive
I ∗ (δ←
computation of I ∗ (δse , X) in Step 6. Finally, the interval of
best improvement is selected among those that end at T and
the optimal clock is reconstructed by backtracking from this
interval using bt() (Steps 10-11).
DP Complexity: Alg. 1 runs in time O(|X|T 3 ), where |X|
denotes the number of all activations in all cascades. This is
due to the nested loops (Steps 4-9) which consider all O(T 2 )
intervals and the maximization in line 6 which iterate over
O(T ) preceding intervals of the current δse . The complexity
does not depend on the full graph G(V, E), since only nodes
participating in the cascades and downstream neighbors need
to be considered (the likelihood of non-active nodes without
active neighbors can be computed in constant time for any
interval). In addition, when there are time steps without activations one can “drop” such intervals in a pre-processing step,
effectively letting activations define the original time points.
In this case the complexity becomes effectively O(|X|4 ).
While DP solves OC exactly in polynomial time, its complexity is prohibitive for large real-world instances. GR is a
top-down greedy approach that scales almost linearly, adding
one partition at a time by splitting existing intervals, starting
from the default clock ∆max . The greedy aspect is in the
selection of the next split based on maximum improvement of
the score.
The steps of GR are outlined in Alg. 2. It initializes the

solution with the default aggregate clock ∆max (Step 1) and
computes all active edges Ea within cascades such that the
source and destination are active preserving the temporal order
(Step 2). It then iteratively tries to add groups of independent
cuts C that do not intersect common active edges in Steps
3-12. C is empty at the beginning of each iteration (Step 4).
The inner loop (Steps 5-10) is essentially a modified sweep
line algorithm in 1D [16], where the segments are defined
by active edges in Ea . Going from small to large times t of
all activations in X, we first add active edges that “end” at t
to Ea (t) (Step 6) and recompute the improvement I(Ea (t))
based on “current” active edges Ea (t) and based on whether
they have been already cut by previous sweeps (Step 7). If the
improvement at time t exceeds 0, we attempt to add the cut
(t, Ea (t)) to the C (Step 8). A cut is added if (i) it does not
have shared activations with any other cut in C, or (ii) in the
case it does, it is added if its improvement exceeds that of the
unique cut it shares active edges with. This logic in add-ordrop()(Step 8) ensures that C maintains the set of independent
time cuts of highest improvement at every round of the outer
loop. In Step 9 we remove active edges ending at t, since they
will not be considered at t + 1. If C is not empty (Step 12)
we add all cuts to ∆ and update their active edges to a cut
state, which affects the improvement computations on Step 7
in subsequent iterations. Finally, if no new cuts were identified
we terminate the loop and return the clock (Steps 12-13).
GR complexity: Each sweep requires O(|X| log(|Ea |)) time,
since we move through the activations and maintain the currently active edges (that enter and exit only) once the structure
Ea (t), where the log factor comes from maintaining them in
a heap structure that support add (Step 6) and delete (Step
9). Since |Ea | grows slower than O(|X|2 ) the sweeps take
O(|X| log(|X|)). Generating all |Ea | in Step 2 might in general
be higher than O(|X| log(|X|)) for very dense networks, but
assuming that the average degree grows as O(log |V |) this step
will not exceed in complexity a single sweep. The number of
sweeps can also reach m = O(|X|) if we make one cut at
a time on every sweep, but such instances will have lots of
overlapping active edges in time. The total time is log-linear
O(m|X| log(|X|)) if we assume that not too many sweeps m
are performed. As demonstrated in the evaluation section, GR
scales near-linearly to large real-world instances and produces
very high-quality solutions (> 90% of optimal).
B. Multi-clock approaches
Unlike OC, kOC is NP-hard. We propose a greedy GRDP
solution and show that it ensures a (1 − 1/e)-approximation.
Theorem 2. I(X|D) is monotonic and submodular as a
function of the set of clocks D.
Proof. The monoticity is due to the maximization in the
definition of the improvement (Eq. 4): I(D ∪ ∆) ≥ I(D),
since in the worst case no node will “select” ∆ rendering the
improvement unchanged due to its addition.
Given two nested sets of clocks D ⊆ C and ∆ ∈
/ C,
let us consider four surjective (onto) functions from nodes
V to clocks: fD , fD∪∆ , fC and fC∪∆ mapping any node v

to the clock (among the set in the function’s subscript) that
maximizes the node improvement. The submodularity property
I(D ∪ ∆) − I(D) ≥ I(C ∪ ∆) − I(C),
holds due to the following three possibilities for any v ∈ V :
• fD∪∆ (v) 6= ∆. This implies that fC∪∆ (v) 6= ∆. As a result
fD (v) = fD∪∆ (v) and fC (v) = fC∪∆ (v), and v contributes
zero to both sides of the inequality.
• fD∪∆ (v) = ∆ and fC∪∆ (v) 6= ∆. Then v makes a positive
contribution to the LHS and zero contribution to the RHS.
• fD∪∆ (v) = fC∪∆ (v) = ∆. Then v contributes positively to
both sides. However, I(v, ∆) ≥ I(v, C) ≥ I(v, D) because fC
has access to all of the clocks that fD does; it will not assign
v to a lower-scoring clock.
Corollary 1. [Apx. of GRDP (due to [11])] A greedy
selection of k clocks ensures a (1 − 1/e)-apx. for kOC.
To construct a Greedy solution for kOC we need to be able
to find the best next clock ∆ to add to an existing solution
of selected clocks D. Let fD (v) be a surjective function
mapping every node to the clock ∆ ∈ D that maximizes the
improvement due to v in all cascades I(v, X|∆). Generalize
the improvement of a node given previous clocks D as:
I(v, X, δse ← δbs−1 |D) =
max{0, I(v, X, δse ← δbs−1 ) − I(v, X|fD (v))}, (8)
where I(v, X|fD (v)) is the improvement due to v’s activation
as part of cascade X in the best clock that v is mapped to
in the solutions so far fD (v). We can similarly generalize the
definitions in Eqs. 6, 7 to account for already selected clocks
obtaining the total interval improvement I(δse ← δbs−1 , X|D)
and the optimal interval improvement I ∗ (δse , X|D) by using
I(v, X, δse ← δbs−1 |D) in the corresponding definitions. Based
on the above, we generalize DP (fD (v)) to return the clock
of best improvement given a selected clocks set D by passing
an additional parameter fD (v) and replacing all improvement
functions in DP (Steps 2,6,7,10) with the corresponding improvements given D. The overall GRDP algorithm starts with
an empty set of clocks and incrementally adds the next best
clock returned by DP (fD (v)).
GRDP selects the best next clock greedily and is, thus,
guaranteed to return a solution of at least (1 − 1/e)OP T due
to Corr. 1. It, however, has a complexity O(k|X|4 ).As a fast
alternative, we also extend GR (Alg. 2) to obtain a doublegreedy GR2 scheme. It also calls incrementally a version
of GR (fD (v)) with the additional parameter that allows for
improvement evaluation, conditional on the best node scores
from previously selected clocks D in (Step 7) of Alg. 1. The
complexity of GR2 is O(k|X|2 ) in the worst case.
IV. E XPERIMENTAL EVALUATION
We evaluate the scalability and quality of our methods
for optimal clock detection and demonstrate their utility for
several applications in both synthetic and real world data. All
experiments are performed on a single core conventional PC
architecture and implemented in Java (single-threaded).
Evaluation datasets are summarized in Tbl. II. Our Twitter
dataset includes propagation of URLs over two months within

P
¯
|E|
|X|
|X| min|X| Duration
2200 5000 185k
30
N/A
1.2m 7685 117k
5
3/12-4/12
4.2m 278
200k
500
9/04-3/09
8.4m 3176
1m
200
9/04-3/09
TABLE II
DATASETS USED FOR EVALUATION .

2

1

0

|V |
Synthetic
1000
Twitter [13] 3331
Flickr-s [4]
66k
Flickr-b [4] 127k

01-Mar

13-Mar

25-Mar

06-Apr

18-Apr

30-Apr

(a) Clocks Twitter (conservative news)
∆0 :
∆1 :
∆2 :

|∆|
163
739
193

|V | %I
1038 83
226 16
8
1

(b) Clock statistics
Fig. 3. Example of a kOC solution in Twitter for 500 conservative media
cascades obtained by GR2 . (a): Interval separators over the period 03/1204/12 for the first three clocks: ∆0 , ∆1 , ∆2 . (b): Statistics of the clocks,
their mapping to nodes and % improvement towards the final solution.

a snowball subnetwork of the Twitter follower graph including
3.3k users [13]. We expand shortened URLs from tweet messages and focus on domains of popular news and commentary
websites (e.g. foxnews, breitbart, thehill) as well as photo and
video domains, e.g. youtube, instagram, etc. Unique URLs
tweeted by at least 5 nodes form individual cascades resulting
in 7.6k cascades and 117k total activations.
We also employ anonymized data from Flickr including
friendship links and favourite photo markings from [4]. We
treat each photo as a cascade over the friendship graph initiated
by the owner of the photo (first activation) while subsequent
users marking the photo as a favorite comprise the rest of
the activation events within the photo cascade. We create two
datasets for evaluation: all cascades of sizes exceeding 500
(Flikr-s) and all cascades of sizes exceeding 200 (Flikr-b).
We also scale-free structured synthetic networks of at least
1000 nodes and sample IC cascades (pn = 0.1, pe = 0.001).
To simulate the temporal heterogeneity of real-world activations, we randomly stretch each original time step to multiple
time steps and distribute its activations uniformly in the
resulting time steps. This ensures that the relative order of
non-simultaneous activations is conserved.
A. Clock discovery: scalability, quality and stability
We first evaluate our solutions and discuss obtained clocks
in real and synthetic data and than move on to several
applications. The clocks obtained by applying GR2 (k = 3) to
the Twitter network are presented in Fig. 3. The very first
clock ∆0 exhibits a relatively more regular partitioning of

the timeline compared to the following clocks (Fig. 3(a)).
Intuitively, it captures the best overall time partitioning that
best explains all underlying cascades. The following clocks
“improve” the resolution for activations of certain nodes in
the network. About 25% of the nodes get assigned to the
second clock ∆1 and less than a tenth of a percent of the
nodes to clock ∆2 (Tbl. 3(b)). Similar diminishing returns are
also observed in the percentage of improvement to the overall
likelihood contributed by each clock (Col: %I in Tbl. 3(b)).
Scalability and quality. We investigate the relative quality
of the clocks obtained by GR and various homogeneous
aggregations of time compared to the optimal solution ∆opt
found with DP for a single clock (OC) in terms of relative
likelihood improvement I(∆)/I(∆opt ) in Fig. 4(a). GR’s
improvement consistently exceeds 90% of the optimal. We also
plot the results for homogeneous time aggregations of fixed
windows of 1 through 10 original time steps. As expected,
no homogeneous clock will work as well because activation
rates vary with time, requiring a varying data-driven temporal
resolution. When the temporal resolution is too high, the
cascades are fragmented; while when it is too low, many
activations appear spontaneous. Only by allowing the resolution to change with time (i.e. OC solutions) do we obtain
an effective model of cascade behavior. GR’s near-optimal
solution quality is critical, since DP algorithm does not scale
to large instances, namely its execution time exceeds 1.5h on
even modest instance sizes Fig. 4(b). In contrast, GR scales
nearly linearly with the number of activations and discovers
high-quality clocks in real-world data with as many as one
million activations (see Fig. 5(c)).
In the multi-clock (kOC) setting, we observe similar trends
for GRDP and GR2 . While GRDP provides a guarantee of a
(1 − 1/e)-approximate solution, its reliance on DP limits its
scalability to large instances. As observed in Figs. 4(c),4(d),
the quality of GR2 ’s solutions closely match those of GRDP
with more than an order of magnitude execution speed-up.
We perform similar evaluation on Twitter and Flickr data
as well. The quality trends for Flickr-b for a single clock
discovery are presented in Fig. 5(a). Ideally one should
compare I(∆) to I(∆opt ) (found using DP), as we did in
Fig. 4(a); however, because these networks are larger, this was
impractical for all but the smallest instances. GR’s improvement score closely matches that of DP up to 200 activations
and persistently dominates fixed-width aggregations for larger
instances. Similar behaviour in terms of quality is observed for
Twitter OC and for both datasets for multiple clock discovery
kOC (figures omitted due to space constraints).
Fig. 5(c) shows the runtime for GR on our three real-world
data sets. Of particular interest is the fact that Twitter, though
a much smaller instance, requires greater execution time for an
equivalent number of activations than Flickr. This is because
running time of GR is affected by the network density and
our Twitter network is much denser. Sparser data (e.g. using
@mentions instead of follows) would likely allow for much
faster execution. While the largest size of Flickr-b requires
several hours to extract a clock, it is worth mentioning that it

600

100

# of activations

600
# of activations

(a) Quality

(b) Time

2

3

1

Time (s)
4

100

10k

1

GRDP 500
GR2 500

0.01

100

GRDP 300
GR2 300

0

DP
GR

0

AGG5
AGG10

I(∆)
750 1500

Time (s)
3000 6000

I(∆) / I(∆opt)
0.5
1.0
0.0

GR
MIN
AGG2

1

k

(c) Quality kOC

GRDP 300
GR2 300
2

GRDP 500
GR2 500
3
4

k

(d) Time kOC

10k
1k

Time (s)

I(∆)
30k

100

60k

GR

2000

3000

AGG20
AGG5
MIN
GR
DP

Twitter
Flickr−s
Flickr−b

0

0

10

1000

I(∆)

B. Applications of optimal clocks

90k

4000

Fig. 4. Solution quality and execution time for synthetic data. (a) Comparison against the optimal improvement score I(∆opt ) for the clock found by GR
and several homogeneous clocks. (b) Comparison of execution time for DP and GR. (c),(d) Solution quality I(∆) and execution time vs number of clocks
discovered by GRDP and GR2 on two datasets, one with 300 activations and one with 500 activations. Note that I(∆) increases with more activations, as
there are more possiblities for improvement over the baseline clock ∆max .

0

300

600

900

# of activations

(a) Flickr-b Quality

0.00

0.25

0.50

Intv. length / |T|

(b) Reg. Clock Quality

250k

1M

|X|

(c) Time

Fig. 5. (a): Likelihood improvement of GR compared to DP and homogeneous
clocks (AGGX, MIN) in Flickr. Similar quality trends persist for GR2 versus
GRDP in Twitter and using multiple clocks (omitted due to space limitation).
(b): Comparison of many different homogeneous clocks to GR using 19k
activations on Flickr-s. (c): Execution time for detecting a single clock in all
three real datasets. Multiple clock detection (omitted) shows an increase in
runtime that is linear in k.

processes a million activations in a 8.4m-edge network with
effectively 10s of millions of active edges. For kOC, the trends
are the similar to those in synthetic data (omitted due to space).
Most notably, GR2 remains linear in k, since it performs the
same call to DP for each round of clock discovery.
Sensitivity to pn and pe . IC’ propagation pn and spontaneous
activation pe probabilities are the only two parameters for our
algorithms. Hence, a natural question is: How stable is the
clock w.r.t. these probabilities? In practice pe and pn have
minimal impact on the produced clocks for large ranges of
their settings. We performed both synthetic and real-world data
experiments that systematically vary both parameters, namely
pe
pn taking values between 0.001 (i.e. spontaneous activations
are very unlikely) and 1 (i.e. activations are equally driven by
external sources and the network). The clocks detected by our
algorithms in synthetic data were identical in all cases where
pe < pn ; only when the parameters were equal was there a
change in the optimal clock. For real-world data, there was
more sensitivity with some changes appearing at pe ≥ 0.2pn ;
however, even in these cases the obtained clocks were largely
unchanged. Note that large settings of pe (comparative to pn )
attempts to fit to a diffusion process that is predominantly
driven by external forces due to the sheer number of nodes,
and hence the network structure’s effect is minimal.

Next we apply detected clocks for improved missing cascade data and cascade size and topic prediction.
Inferring missing cascade activations. Due to limitations on
API usage of OSNs or privacy restrictions, only a partial observation of the diffusion process are typically available [20, 5,
14]. Hence, in order to accurately detect information sources,
estimate virality along edges or maximize the influence of
campaigns it is important to infer unobserved cascade participants based on the network structure and the partially available
cascade information. Zong et al. [20] study this problem in the
context of IC and propose approximate algorithms for the NPhard problem of optimal cascade reconstruction.
To illustrate the importance of using an appropriate network
clock for this application, we adopt the WPCT algorithm [20]
to infer missing activations in both synthetic and real-world
data, while comparing the accuracy due to the original and
optimal clocks. WPCT attempts to reconstruct a feasible
cascade tree based on partial observed activations. A cascade
tree is feasible if the distance from a cascade’s source to
every observed activation is equal to the time of activation
(assuming the source is activated at t = 0). To allow for
cascades with multiple sources, we use a modified version of
WPCT that returns a forest so long as all observed activations
are reachable from one of the cascade sources. Because
this is an NP-hard problem [20], the algorithm may fail to
find such a forest even when one exists. Working with an
appropriate timeline, thus become critical for the algorithm
and the completion applications overall.
The success rate of WPCT in finding a viable forest
(measured as the fraction of cascades that obtained feasible trees) is one measure of performance and the quality
of predicted missing activation a second one. To test the
algorithm, we begin with complete cascades and then hide
activations, removing them from the data provided to WPCT.
Each activation in a cascade has a fixed probability of being
removed independent of all other activations, except that the
first and last activation of each cascade are always kept since
the algorithm has no chance of discovering them. Considering
these hidden activations as true positives and any other nonobserved nodes as false positives, we measure precision and
recall for obtained solutions.

0.4

0.5

Fraction of hidden activations

(e) Twitter success

0.2

0.4

0.6

0.8

0.2

Fraction of hidden activations

0.3

0.4

0.5

Fraction of hidden activations

(f) Twitter recall

0.4

0.6

0.8

Fraction of hidden activations

(d) Synthetic F1

0.4

Recall

0.6

0.6

(c) Synthetic success

Success rate
0.2

0.4
0.0

5

0.0
0.1

0.2

F1−measure

0.4
0.0

4

0.10

Recall
0.3

3

(b) Synthetic F1 stretch

0.00

Success rate

0.0 0.2 0.4 0.6 0.8

0.2

2

Avg. interval length

(a) Synthetic Success stretch

0.1

0.2

Success rate

0.20
1

GR
MIN
AGG−match

0.2

5

0.0

4

0.4

3

Avg. interval length

0.2

2

0.10
0.00

F1−measure

0.6
0.4
0.2

Success rate

0.0
1

GR
MIN
AGG−match

0.1

0.2

0.3

0.4

0.5

Fraction of hidden activations

(g) Flickr success

0.1

0.2

0.3

0.4

0.5

Fraction of hidden activations

(h) Flickr recall

Fig. 6. Comparison of solution quality for the cascade completion problem in [20]. M IN are results using the original timings (∆min ). GR are results
after remapping times according to the clock found by our greedy algorithm. AGG-match are results after remapping times onto a homogenous clock with
the same number of intervals as the one found by GR. (a)-(d) show synthetic data; (e)-(h) show real-world data.

To generate synthetic data for this experiment, random
cascades with at least 30 activations were created on a fixed,
scale-free network. To emulate the delays in a real-world network, these cascades were then stretched: a random clock with
a known average interval length was generated, and then each
cascade had its times remapped onto that clock. For example,
if the third interval in a clock was h5, 8i, then an activation
at t = 3 would be remapped randomly onto a time between
5 and 8, inclusive. The results on synthetic data are shown in
Figs.6(a)-6(b). Each figure shows three traces: the result after
applying the clock found by GR, the result after applying a
homogeneous clock with the same number of intervals as the
GR clock (AGG-match), and the baseline (MIN) using the
original timeline (∆min ). Using the GR clock greatly increases
the success rate when cascades have been stretched, which
would be the case when the temporal resolution is too high.
It also outperforms both alternatives for any rate of hiding
activations from the algorithm. The spike in success rate at
extremely high hidden-activation rates (Fig. 6(c)) stems from
the removal of constraints. To complete a cascade tree, one
of simply needs to recover any path from source to the few
remaining activations of appropriate length. The prediction
of missing nodes (F1 measure), however, decreases for large
drop rate due to the large number of possible candidates
Fig. 6(d). Essentially, while the recall for such cases is still
high, precision decreasses drastically.
In real-world data, we only vary the probability of hiding
activations. Both networks are quite dense, resulting in huge
number of candidates for completion and thus high false
positive rates in all cases; hence, we only plot recall instead of
F1 -measure. The Twitter network is so dense that the homogeneous clock outperforms GR on the success rate measure
(Fig. 6(e); there are so many possible paths that at a matching
level of temporal resolution (same number of intervals as in
a GR clock, but homogeneous in length), it becomes very
likely that a feasible tree can be found. Most of these solutions

Data

m
F1 w/o Clock F1 w Clock
#casc.
10
0.67
0.67
1280
Twitter
20
0.66
0.71
664
30
0.7
0.76
309
300 . . . 500
0.66
0.66
1177 . . . 271
Flickr-b
600
0.62
0.69
173
700
0.61
0.67
94
TABLE III
C ASCADE SIZE PREDICTION AIDED BY DETECTED CLOCKS .

are, however, incorrect, as indicated by the much lower recall
rate of AGG-match than that of GR in Fig. 6(f). In Flickr’s
less-dense network, GR outperforms both alternatives on both
metrics (Figs. 6(g)-6(h)).
Predicting cascade size based on initial observations is
another relevant application we consider. Recently Cheng et
al [6] considered multiple features of the m-prefix of observed
cascades (the first m activations) to predict the eventual size
of cascades.The authors observed that temporal features have
highest impact on prediction accuracy [6]. Naturally, precisely
these features will be most affected by inappropriate temporal
aggregations of the timeline. For example, in cascades initiated
late at night, observing a large time-lag to the morning activations might make the cascade prefix appear slow-growing
and bias its prediction to limited future growth. Hence, we
investigate the potential for improvement of size prediction
based on learned network clocks.
We employ only the temporal features proposed in [6]
and set-up the same prediction problem: given the first m
activations, how likely is it that a cascade exceeds size
αm, α ≥ 1? We set α such that the considered cascades
are balanced between the small (|X| < αm) and large
(|X| ≥ αm) class. In [6], α was set to 2 as this produced
balanced prediction problems, however, the appropriate setting
for our datasets is α ≈ 1.5, as our cascade size distributions
have a different slant. We compare the F1-measure in crossvalidation of the temporal features according to (i) the original
times of activation (col. 3 in Tbl. III) and the same according

Comparison
#acts. per class min|X| #casc. ACC
Liberal v.s. Conservative
5301
30
55
56.2%
Text v.s. Visual
15132
20
342 57.5%
TABLE IV
C ASCADE TOPIC PREDICTION AS A PROXY FOR CLOCK CONSISTENCY.

to the clock obtained by GR (col. 4 in Tbl. III), considering
prefixes of increasing size m in Twitter and Flickr.
In Twitter the optimal clock enables 7% lift of the F1
measure for m = 20 and 8% for m = 30, and performs on
par with the original clock for shorter prefixes. A significant
improvement due to the optimal clock in Flickr occurs for
prefixes of size 600 and higher. The cascades in Flickr tend
to be very large and a big number of the original activations
are disconnected in the network and hence do not allow the
clock to boost the informativeness of the features. This might
be due to many popular photos being featured, thus inducing
non-network driven favorite markings. The optimal clock
provides a significant prediction improvement (m ≥ 600) and
if combined with possible other features (tags,text) it might
aide to even better performance for actual prediction.
Topical consistency of clocks. Do similar topics and information types spread similarly in the network? In this application,
we are interested to quantify the level of consistency of the
optimal clocks for information of the same type. We use
clock-based cascade topic prediction quality as a proxy for
clock consistency. We prepare two classification tasks listed
in Tbl. IV. In the first case we select URLs from liberal
(Huffington post and the hill) and conservative (Breitbart and
Foxnews) outlets such that the total number of activations
match in each class and we predict (using leave-one-out
validation) the accuracy of placing a cascade in its own
category simply based on the likelihoods of the cascades
according to the two clocks detected based on the remainder
of the categories. We repeat the same for news URLs (Text)
versus Visual content (photo/video).
The accuracy in both settings is significantly above random
(50% will be random due to the balanced number of activations
per class and, thus, similar size clocks). This observation
alludes to different content spreading according to different
conserved clocks—a direction we plan to pursue in the future
after obtaining a larger annotated corpus of simultaneous
cascades. Similar evaluation is not possible in Flickr as the
data is anonymized. It is also important to note that the clock
likelihood is not the best predictor of cascade topic (e.g.
content and users profiles would likely yield much higher
quality), however, we use this task only as a proxy for clock
consistency within topics/content.
V. R ELATED W ORK
To the best of our knowledge, we are the first to propose
algorithms for model-driven heterogeneous time aggregations
of dynamic network data on information cascades. Previously,
varying time windows have been proposed by Yang et al [19]
to mine progression stages in event sequences; however, this
work assumes independent sequences and no network structure involved, while we are interested in network diffusion

processes. The effect of homogeneous temporal aggregations
of the timeline in dynamic networks is a better-studied [12,
3, 17, 2]. Different fixed window sizes and their effect of the
resulting smoothness of time series of network statistics was
consisdered in [17, 3]. Significant differences in the structural
features of networks formed by aggregating mobile phone call
records at different resolutions was observed in [12], and the
effect of aggregation window size on predicting changes in
the network was studied in [2].
All above problems clearly demonstrate the need to select
an optimal aggregation for evolving networks. However, the
focus in all of them is on smoothness of global or local
network statistics and the proposed approaches select a homogeneous time scale, i.e. each aggregation window is the
same length of time. We demonstrate in experiments that
such homogeneous aggregations are inadequate for explaining
observed information cascades, while our in-homogeneous
network clock solutions are superior in terms of likelihood
of observed cascades and for several applicatios.
Other approaches for cascade completion were also considered [14], as well as the problem of missing data when
trying to limit cascades [1]. Providing information about the
optimal clock to such algorithms could potentially improve
their overall performance similar to the ones we considered.
Other applications to which clock data could be applied
include influence maximization [10] and estimation of the
diffusion probabilities of IC [15].
VI. C ONCLUSION
We proposed network clocks: heterogeneous partitions of
the timeline that best explain observed information propagation cascades in real-world networks with respect to the independent cascade model (IC). We showed an optimal dynamic
programming solution DP for the single optimal clock (OC)
problem and a scalable greedy alternative GR that matches
(within 10%) DP’s quality, but is able to detect clocks in
an 8.4-million-edges Flickr network and more than a million
activations of nodes within cascades. We demonstrated that
the multi-clock problem (kOC) is NP-hard and proposed both
a (1 − 1/e)-approximation GRDP and a fast and accurate
heuristic GR2 . The detected clocks enable improved cascade
size classification (up to 8% F1 lift) and improved missing
cascade data inference (0.15 better Recall) in Twitter and
Flickr, compared to using the original time or fixed-window
aggregations of time.
R EFERENCES
[1] C. Budak, D. Agrawal, and A. El Abbadi. Limiting the spread of
misinformation in social networks. In ACM WWW, 2011.
[2] M. Budka, K. Musial, and K. Juszczyszyn. Predicting the evolution of
social networks: optimal time window size for increased accuracy. In
Proc. PASSAT SocialCom, pages 21–30. IEEE, 2012.
[3] R. S. Caceres, T. Berger-Wolf, and R. Grossman. Temporal scale of
processes in dynamic networks. In IEEE ICDM Workshops, 2011.
[4] M. Cha, A. Mislove, and K. P. Gummadi. A Measurement-driven
Analysis of Information Propagation in the Flickr Social Network. In
Proc. WWW, Madrid, Spain, April 2009.
[5] Z. Chen, H. Tong, and L. Ying. Full diffusion history reconstruction in
networks. In Proc IEEE Big Data, 2015.

[6] J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, and J. Leskovec.
Can cascades be predicted? In Proceedings of the 23rd international
conference on World wide web, pages 925–936. ACM, 2014.
[7] J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex
systems look at the underlying process of word-of-mouth. Marketing
letters, 12(3):211–223, 2001.
[8] J. Goldenberg, B. Libai, and E. Muller. Using complex systems analysis
to advance marketing theory development: Modeling heterogeneity
effects on new product growth through stochastic cellular automata.
Academy of Marketing Science Review, 2001:1, 2001.
[9] M. Granovetter. Threshold models of collective behavior. American
journal of sociology, pages 1420–1443, 1978.
[10] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of
influence through a social network. In Proc. ACM SIGKDD, pages
137–146. ACM, 2003.
[11] A. Krause and D. Golovin. Submodular function maximization. In Chapter in Tractability: Practical Approaches to Hard Problems. Cambridge
University Press, 2012.
[12] G. Krings, M. Karsai, S. Bernhardsson, V. D. Blondel, and J. Saramäki.
Effects of time window size and placement on the structure of an
aggregated communication network. EPJ Data Science, 1(4):1–16, 2012.
[13] K. Macropol, P. Bogdanov, A. K. Singh, L. Petzold, and X. Yan. I act,
therefore i judge: Network sentiment dynamics based on user activity
change. In Proc. of the 2013 IEEE/ACM Int’l Conf. on Advances in
Social Networks Analysis and Mining, pages 396–402. ACM, 2013.
[14] E. Sadikov, M. Medina, J. Leskovec, and H. Garcia-Molina. Correcting
for missing data in information cascades. In Proc. of the fourth int’l
conf. on Web search and data mining, pages 55–64. ACM, 2011.
[15] K. Saito, R. Nakano, and M. Kimura. Prediction of information
diffusion probabilities for independent cascade model. In Knowledgebased intelligent information and engineering systems, pages 67–75.
Springer, 2008.
[16] M. I. Shamos and D. Hoey. Geometric intersection problems. In
Foundations of Computer Science, 1976., 17th Annual Symposium on,
pages 208–215. IEEE, 1976.
[17] R. Sulo, T. Berger-Wolf, and R. Grossman. Meaningful selection of
temporal resolution for dynamic networks. In Proc. of the Eighth
Workshop on MLG, pages 127–136. ACM, 2010.
[18] A. Tagarelli and R. Interdonato. Time-aware analysis and ranking of
lurkers in social networks. Soc. Net. Anal. and Mining, 5(1):46, 2015.
[19] J. Yang, J. McAuley, J. Leskovec, P. LePendu, and N. Shah. Finding
progression stages in time-evolving event sequences. In Proc. of the
23rd int’l conf. on World Wide Web, pages 783–794. ACM, 2014.
[20] B. Zong, Y. Wu, A. K. Singh, and X. Yan. Inferring the underlying
structure of information cascades. In Data Mining (ICDM), 2012 IEEE
12th International Conference on, pages 1218–1223. IEEE, 2012.

