Reconstructing a cascade from temporal observations
Han Xiao Polina Rozenshtein Nikolaj Tatti Aristides Gionis
cs.SI






































































problemProblem

observationObservation























































































ifpackageloadedalgorithm2e
	tcpas{}
	textnormal
	Nullnull
	ANDand
	ORor
	EACHeach
	Inputinput
	Outputoutput
	KwInputInput
	KwOutputOutput
	textnormal
	Falsefalse
	Truetrue
	Breakbreak
	Nonenone
	Continuecontinue




squishlist
∙
		 
			
			
			
			
			
			  
	



      







positioning,fit,shapes
decorations.pathreplacing
arrows

background
foreground
background,main,foreground

multicircle/.style  args=#1, #2
 alias=tmp@name, 
  postaction=
    insert path=
     
     @node@namecenter
                  @node@nameeast
     @x
     
        [white] (@node@name.center)  circle (-);
        [#2] (@node@name.center)  circle (-);
        [#2] (@node@name.center)  – ++(0:-) arc (0:#1:-)–cycle;
        

















-0pt







@drawtickgridlines@INSTALLCLIP@onorientedsurf#1







yaf
yafcolor1,mark options=scale=0.75,mark=o, 
yafcolor2,mark options=scale=0.75,mark=square,
yafcolor3,mark options=scale=0.75,mark=triangle,
yafcolor4,mark options=scale=0.75,mark=o,
yafcolor5,mark options=scale=0.75,mark=o,
yafcolor6,mark options=scale=0.75,mark=o,
yafcolor7,mark options=scale=0.75,mark=o,
yafcolor8,mark options=scale=0.75,mark=o 

axis y line=left, axis x line=bottom,
  tick align=outside,
  compat = 1.3,
  tickwidth=,
  clip = false,
  every axis title shift = 0pt,
    x axis line style= -, line width = 0pt, opacity = 0,
    y axis line style= -, line width = 0pt, opacity = 0,
    x tick style= line width = , color=yafaxiscolor, yshift = ,
    y tick style= line width = , color=yafaxiscolor, xshift = ,
    x tick label style = font=, yshift = ,
    y tick label style = font=, xshift = ,
    every axis y label/.style = at = (ticklabel cs:0.5), rotate=90, anchor=center, font=, yshift = -,
    every axis x label/.style = at = (ticklabel cs:0.5), anchor=center, font=, yshift = ,
    x tick label style = font=, yshift = 1pt,
    grid = major,
    major grid style  = dash pattern = on 1pt off 3 pt,
  every axis plot post/.append style= line width= ,
  legend cell align = left,
  legend style = inner sep = 1pt, cells = font=,
  legend image code/.code=
    [mark repeat=2,mark phase=2,#1] 
    plot coordinates  (0cm,0cm) (0.15cm,0cm) (0.3cm,0cm) ;
   






 













[R]Copyright © 2018 by SIAM

      Copyright for this paper is retained by authors












































































Reconstructing a cascade from temporal observations
    
Han Xiao^⋆   Polina Rozenshtein^⋆   Nikolaj Tatti^†   Aristides Gionis^⋆ 


^⋆Aalto University     ^†F-Secure 

Espoo, Finland     Helsinki, Finland 

     









    
==========================================================================================================================================================================


















Given a subset of active nodes in a network
can we reconstruct the cascade that has generated these observations?
This is a problem that has been studied in the literature, 
but here we focus in the case that 
temporal information is available about the active nodes. 
In particular, 
we assume that in addition to the subset of active nodes
we also know their activation time. 

We formulate this cascade-reconstruction problem 
as a variant of a Steiner-tree problem:
we ask to find a tree that spans all reported active nodes
while satisfying temporal-consistency constraints.





We present three approximation algorithms. 
The best algorithm in terms of quality
achieves a (√())-approximation guarantee, 
where is the number of active nodes, 
while the most efficient algorithm has linear­ithmic running time, 
making it scalable to very large graphs.

We evaluate our algorithms on real-world networks with both simulated and real cascades. 
Our results indicate that utilizing the available temporal information 
allows for more accurate cascade reconstruction.
Furthermore, our objective leads to finding the “backbone” of the cascade
and it gives solutions of high precision.





§ INTRODUCTION


Ideas, behaviors, computer viruses, and diseases, spread in networks. 
People are 
influencing each other
adopting behaviors, innovations, or memes.
Diseases like flu or measles are transmitted from person to person, 
while computer viruses spread in computer networks.
The study of diffusion processes has been a central theme in network science and graph mining.
Topics of interest include modeling diffusion processes <cit.>, 
devising strategies to contain the spread of epidemics <cit.>,
maximizing the spread of influence for marketing purposes <cit.>,
as well as identifying starting points and missing nodes in cascades <cit.>.

In this paper 
we consider the problem of reconstructing a cascade
that has occurred in a network, given partial observations.
We model the problem by considering a graph 
=(, )
and a subset of nodes '⊆
that have been activated/infected during the cascade
(people who have fallen sick, users who have adopted an innovation, etc.).
The goal is to 



infer the hidden cascade
and reconstruct
other possible active nodes.
Previous approaches on this problem make assumptions about the underlying  
diffusion models, such as 
the susceptible-infected model () <cit.>
or the independent-cascade model () <cit.>, 
or consider additional information, such as 
the exact time of all network interactions <cit.>.



Our approach to the cascade-reconstruction problem 
is to utilize temporal information about the active nodes. 
In particular, we consider that for all observed active nodes
the activation time is known. 
This is a realistic assumption in many settings, 
e.g., it is often easy to determine when a patient got sick. 

However, we still consider the case of partial observations, 
i.e., ' is a subset of all active nodes in the cascade. 







A simple example is illustrated in Figure <ref>.
A ground truth cascade is depicted in the left side. 
Only a subset of the infected nodes are known, 
and for those nodes we also know their infection time,
which is indicated by the colorbar in the right.
A cascade reconstructed by our algorithms, 
for this problem instance, is shown in the right side. 
The reconstructed cascade is required to parsimonious and to respect
the node infecting order induced by the input infection times.
We note that we do not make any assumption about the diffusion model; 
we only rely on parsimony and ask to find the smallest cascade
tree that is consistent with the observed data. 
Formulated in this manner, our approach is able to find the most important nodes
of the cascade and thus, it gives solutions of high precision.

A simple motivating example of our setting and the main idea
of our approach is illustrated in Figure <ref>:
a graph G with nodes {u,v,w,x,y} is shown, where a cascade has occurred.
Nodes u, v and w are active (they participate in the cascade), 
while it is not known whether nodes x and y are active (they may be).
For simplicity we assume that there is one seed node.
Given only this information and making no assumption about the diffusion model, 
parsimony suggests that the simpler cascade that explains the observed data 
is one that involves only the nodes u, v and w.
The reason is that since nodes u, v and w are connected in the graph, 
a cascade that involves only those nodes is possible to occur.

Imagine now that activation times t_u, t_v, and t_w, 
are provided for the three active nodes  u, v, and w, respectively, 
and assume that t_u < t_w < t_v.
In this case, 
parsimony suggests that a simple cascade that explains the observed data 
is one that involves all 5 nodes {u,v,w,x,y}.
Furthermore, we can infer that u is the seed node, 
while x was activated second and y was activated third,
followed by w and v 
(the relative order between v and w 
cannot be inferred with certainty and it depends on activation delays).


From the technical viewpoint, 
we formulate the cascade-reconstruction problem as a Steiner-tree problem.
Given the reported active nodes and their activation timestamps, 
we seek to find a tree that spans all reported nodes, 
while all rooted paths in the tree preserve the order of the observed timestamps. 
We refer to such a tree by order-preserving Steiner tree
and to the problem we study by .
This is a novel Steiner-tree problem variant.

For the proposed problem
we develop three approximation algorithms. 
The first algorithm, , 
uses the metric closure of the graph induced by the reported active nodes:
it constructs a directed graph, finds a minimum spanning tree on that graph, 
and builds a cascade tree based on the minimum spanning tree.
The second algorithm, , 
is a simplification of and it builds a cascade tree directly from the reported active nodes, 
without finding a minimum spanning tree on the metric closure. 
The third algorithm, , 
builds the cascade tree by a modified breadth-first search ()
that takes into account the activation timestamps to delay certain search branches.

All three algorithms come with provable approximation guarantees. 
Assuming that the number of reported active nodes is , 
provides a (√())-approximation guarantee
while both and give a -approximation guarantee.

In practice, when compared to a lower-bound obtained by the standard (non-temporal) Steiner-tree problem, 
all three algorithms give much better solutions than it is suggested by the theoretical guarantee.

In terms of scalability, 
the running time of and is ( + ^2) and () respectively, 
where  is the number of edges of the graph . 
On the other hand, runs in time ( + log), 
making it an extremely scalable algorithm, 
able to cope with very large graphs and large number of reported active nodes.

In summary, our contributions are as follows. 


  * We present a novel formulation of a Steiner-tree problem 
with ordering constraints, 
which models the problem of reconstructing a cascade
from partial observations with temporal information.

  * For the proposed Steiner-tree problem
we provide three approximation algorithms. 
The best algorithm in terms of quality
achieves a (√())-approximation guarantee
and has running time ().
The most scalable algorithm 
achieves a -approximation guarantee 
and has running time ( + log).

  * We experimentally evaluate the proposed algorithms
on real-world networks
using cascades simulated with different diffusion models.
Comparison with the baseline Steiner-tree algorithm
that does not use temporal information, 
shows that incorporating timestamps in the problem setting
does not lead to significant loss in solution quality (as measured by the objective function)
while allowing to find other active nodes with better predicted activation time.


The rest of the paper is organized as follows. First, we discuss the related work in Section <ref>. 
Then we introduce necessary notation and definitions in Section <ref>. 
Section <ref> presents the problem formulation, followed by Section <ref> 
where we discuss and analyze our approximation algorithms. 
In Section <ref>, we evaluate the performance of the proposed algorithms,
and Section <ref> concludes the paper.









§ RELATED WORK



Diffusion processes have been widely studied in general. 
However, the problem of “reverse engineering” an epidemic has received relatively little attention.
Shah and Zaman <cit.> formalize the notion of rumor-centrality 
to identify the single source node of an epidemic under the susceptible-infected model (), 
and provide an optimal algorithm for d-regular trees.
Prakash et al. <cit.> study
the problem of recovering multiple seed nodes under the  model using the 
minimum-description length principle () —
i.e., as in this paper a parsimony principle is used.


Lappas et al. <cit.> study the problem of 
identifying k seed nodes, or effectors, 
in a partially-activated network, 
which is assumed to be in steady-state under the independent-cascade) model (). 
Feizi et al. <cit.> and
Sefer et al. <cit.> address the same problem
(identifying k seed nodes) in the case of multiple snapshots of a graph.
Feizi et al. consider the  model, while Sefer et al. consider 
the susceptible-exposed-infectious-recovered model () model. 
These works consider fully-observed infection footprints and focus only 
on the source-detection problem. 

A recent approach on the cascade-reconstruction problem was proposed
by Rozenshtein et al. <cit.>, 
and like this work temporal network information is used. 
However, unlike our setting, 
Rozenshtein et al. assume that the complete temporal network is given,
i.e., timestamps are available for all edges. 


Thus, the setting is different than the one studied in this paper 
and it makes stronger assumptions about data availability. 

The recent study of Farajtabar et al. <cit.> is one of the closest works to ours. 
However, they consider the problem of identifying a single seed given multiple partially observed cascades. 
and they explicitly assume continuous time diffusion model. 
Another related work is presented by Sundareisan et al. <cit.>, 
who simultaneously find the starting points of the epidemic and the missing infections 
given one sample snapshot and
assuming the  model. 
In contrast, our paper addresses the general problem of reconstructing a cascade, 
given several reported active nodes, and corresponding activation timestamps, 
but without assuming any model.

A different line of research in the area of information cascades
addresses the task of inferring the underlying network structure from sets of observed 
cascades <cit.>.
Typically those works assume that there are no missing nodes in a cascade.
This line of research is fairly distinct than the problem we consider in this paper.


From the theoretical point of view, our problem formulation is a generalization on minimum Steiner-tree problem. This classic -complete problem has a folklore 2-approximation algorithm via minimum spanning tree. However, the order constrains make our problem more related to minimum directed Steiner tree, which is known to be inapproximable to better than logarithmic factor due to reduction from minimum set cover. 
The best known algorithm was developed by Charikar et al. <cit.>. 
and 
recently improved by Huang <cit.>. 
The algorithm constructs the tree by greedy recursion, 
and obtains a guarantee of ℓ(ℓ-1)k^1/ℓ, 
where ℓ is the depth of recursion and k is the number of terminals.
However, the running time is (^ℓ k^ℓ), and thus, impractical.




A related line of research is the problem of inferring the overall  inferring cascade data  graphs from sets of observed cascades <cit.>, though they assume there are no missing nodes in a cascade.


An orthogonal direction of research <cit.> assumes that a full history of interaction is given, while reports are noisy and delayed. 
Both assumption are highly unrealistic. 

One of the closest to our work is Farajtabar et al. <cit.>. However, they consider identifying a single seed given multiple partially observed cascades, assuming the  model. Another related work is by Sundareisan et al. <cit.>, who simultaneously find the starting points of the epidemic and missing infections given one sampled snapshot, assuming the  model. In contrast, our paper addresses the general problem of paths of infection spreading, given several reports of infection, without assuming any model.




§ PRELIMINARIES



We consider an undirected graph =(, ) with nodes and edges.
We assume that a dynamic propagation process is taking place in the network. 


We use the generic term active  
to refer to nodes that have reacted positively during the propagation process, 
e.g., they have infected by the virus, adopted the meme, etc.

We assume that the propagation process starts at some seed node and other nodes become active via edges from their active neighbors.
The activation spread can occur according to an unknown model. 
As we will see, our problem definition and algorithms
rely only on a parsimony principle, 
and do not depend on the underlying activity-propagation model.

We only observe a subset of all active nodes in the graph.
For each observed active node u
we also obtain the time t when u was activated.
The set of active nodes together with their activation timestamps is 
denoted by ={(u,t)}, and it is referred to as reported nodes.


The number of reported active nodes is denoted by ||=.
In many applications we have ≪, 
but this is not a required assumption.
The seed does not necessarily belong in
the set of reported active nodes.

The set of active nodes in (i.e., without timestamps) is denoted by (). 
Similarly, the set of all timestamps in is denoted by ().
We use  to denote the earliest timestamp in ().
If (u, t) ∈, we write t(u) = t. 
The set of all nodes with timestamp t is denoted by (t) = u | (u, t) ∈. 

Consider a candidate seed node r and a reported node (u_1,t_1)∈. 
A path  from r to u_1 is called order-respecting path
if does not contain any reported node (u_2,t_2)∈, with t_2 > t_1.
Note that an order-respecting path can contain two reported nodes with the same timestamp.



§ PROBLEM FORMULATION



Given a graph =(, ) and a set of reported nodes ={(u,t)}, 

our goal is to reconstruct the most likely cascade that has generated the observed data. 
As mentioned before, we do not make any assumption on the underlying propagation model, 
we only assume that a cascade starts at a seed node (which is unknown) 
and proceeds via graph neighbors.
Motivated by a parsimony consideration, such as Occam's razor, 
we can formulate the cascade-reconstruction problem 
as finding the smallest cascade that explains the observed data.
It is clear that such a minimal cascade
consists of a tree  rooted at the seed node 
and containing all the reported nodes in .
Our goal is to infer such a tree . 
Furthermore, we should ensure that the reconstructed tree
is consistent with the observed timestamps in .
One natural way to provide a notion of temporal consistency
is to require that all paths in the reconstructed tree are order-respecting.
The above discussion motivates our problem definition.

[]

We are given a graph =(, ) and a set of reported nodes 
={(u,t)} with u∈ and t∈ 
for a relatively small subset of nodes in .
The goal is to find a seed ∈ and 
a tree  rooted in , such that
	

  (i)
the  spans all the reported nodes (), 

  (ii)
all paths in starting at node  are order-respecting, and

  (iii)
the total number of edges in is minimized. 



Requirements (i) and (ii) ensure that the reconstructed tree
is consistent with the observed data, 
while requirement (iii) quantifies parsimony.

It is clear that for an adversarially-selected subset of reported nodes
it is impossible to reconstruct the ground-truth cascade.
For instance, consider the case that all the nodes in the graph are active,
but the reported nodes are concentrated in a local neighborhood of the graph.
In this case, it is unreasonable to expect from 
any reconstruction algorithm to infer the ground-truth cascade. 

On the other hand, if the set of reported nodes is a “representative” subset 
of the active nodes (e.g., a uniform sample), 
we expect that it will be possible to reconstruct a tree 
that contains the most salient and most central nodes of the cascade. 
In other words, we expect that, compared to all active nodes, 
the set of nodes contained in our reconstructed tree has high precision,
but low recall.

We now proceed to discuss the algorithmic complexity of Problem <ref>.
A first observation is
that we are asking to find both a seed node and a tree rooted in .
A simple way to achieve this
is to consider each node v∈ as a candidate seed, 
find a tree _v rooted in v, 
and return the optimal tree (smallest number of edges) 
among all trees found.

Interestingly, it turns out that one does not need to consider all possible
nodes as candidate seeds. 
Instead the optimal tree is the one that is rooted at the reported node with the 
earliest timestamp.
For the following observation recall that = min().



The optimal solution to the  problem
is a tree rooted at the reported node (u_0, )∈. 
If there is more than one node in the set (), 
any of them can be considered as a root for the optimal tree.


Assume a minimal Steiner tree T, 
rooted in some node .  
Let  be the path from u_0 to . 
The reported nodes in  have all timestamp equal to . 
Let v be a reported node, 
 be a path from v to , and 
' be the path from v to u_0. 
Then ' contains a prefix of  followed by (a part of) . 
Since the reported nodes in  have timestamp equal to , 
it follows that ' is an order-respecting path.
This allows us to re-root the tree from  to u_0
while respecting the order.



A consequence of Observation <ref>
is that we can restrict our attention to problem , 
a variant of where the seed is given as input.

Even though Observation <ref> gives a useful and practical optimization, 
it does not change the computational complexity of the problem we consider.


Problem is .


The standard problem <cit.>, 
with an input graph =(,) and a set of terminal nodes X, can
be reduced to the problem with the same graph =(,) as the input
and reported nodes ={(x,0)}, for each x∈ X.




Problem  is .


All proofs are provided in the appendix.




§ APPROXIMATION ALGORITHMS



The Steiner tree problem, and many of its variants, 
have been studied extensively in the literature. 
Different approximation algorithms are available 
depending on the exact setting and problem variant. 

In the standard Steiner tree problem <cit.>
we are given an undirected weighted graph =(, ), 
and a set of terminal nodes ⊆,
and the goal is to find tree that spans all terminal nodes

and whose total edge weight is minimized. 
For this problem there are several approximation algorithms
with a constant-factor approximation guarantee, 
such an algorithm that uses the metric closure 
of the graph induced by the terminals <cit.>,
or the primal-dual method <cit.>.

The Steiner tree problem on directed graphs is considerably more difficult; 
the best known algorithm, proposed by Charikar et al. <cit.>, 
gives an approximation guarantee
ℓ(ℓ-1)k^1/ℓ, for recursion parameter ℓ>2, 
and has running time (^ℓ k^ℓ),
while it is known that the problem
cannot be approximated with a factor better than 
clog|X|, unless 𝐏=𝐍𝐏.

The problem, proposed in this paper, 
is a novel Steiner-tree variant, 
and thus, new approximation algorithms need to be devised.
The problem formulation assumes an undirected graph,
but ordering constraints are required
to ensure that the reconstructed cascade is consistent with the observed timestamps.
This makes the problem significantly different than 
existing formulations on either undirected or directed graphs.





 §.§ Algorithm based on metric closure


Our first algorithm for the problem
uses the metric closure of the graph induced by the terminals,
and it is an adaptation of the algorithm 
for the standard Steiner-tree problem on undirected graphs.
We call this algorithm .

Some additional notation is needed to present the algorithm.
Consider an instance of , 
i.e., a graph =(,) and a set of reported nodes ={(u,t)}.
Given two reported nodes u and v 
we define the excluding shortest path from u to v 
to be the shortest path from u to v in G(V∖(),E), 
that is, the shortest path that does not use any other reported nodes. 
If there are multiple shortest paths, we select one arbitrarily.
The excluding shortest path from u to v is denoted by (u,v), 
and its length by (u, v) = (u, v).

The algorithm
constructs a weighted directed graph H among the reported nodes. 
Edge directions in H are from terminals of earlier timestamps
to terminals of later timestamps, 
and edge weights correspond to excluding shortest-path lengths.
Next, constructs a directed minimum spanning tree on H rooted in .
Then the algorithm reconstructs a cascade on the original graph by starting from seed and 
processing the terminals () in chronological order:
each new terminal u 
is added to the currently-reconstructed cascade
via the best path that goes through one of its ancestors in the minimum spanning tree on H.
The pseudocode from is given in Algorithm <ref>.

[t]
  
  
  =(,), ={(u,t)}, root ∈()
  Order-respecting 
    rooted in that spans all nodes in ().	Q () 
  
  
  
  
  Construct weighted directed graph H=(Q,X) with X={(u,v): t(u)≤ t(v)} and edge weights 
  w(u,v)= (u,v) 
  A  minimum directed spanning tree of H rooted in  
  ({},∅)  *initially, contains seed and no edge
  u∈() in chronological order
  
    find w so that 
    
    w is in T 
    w is the closest ancestor of u in A 
    
    add path from u to w in A to  
  	
  


We first prove that returns a feasible solution. 


returns an order-respect­ing Steiner tree, which spans .


First, by the for-loop defined in lines 5–9, 
the resulting tree T is a subgraph of , which spans all reported nodes. 
For each new reported node u processed in the for-loop, 
a new path P is added in the subgraph , 
which contains only one node from , and thus  is indeed a tree. 
Moreover, P may contain only the largest time stamps in current .
This makes  an order-respecting Steiner tree.



Next we show that provides a
(√())-ap­pro­xi­ma­tion guarantee —
recall that  =|()| is the number of terminals (reported nodes).



The algorithm provides
approximation guarantee 2(1+√(3/2))√( - 1) for problem .




To prove this result we first need to prove couple of technical lemmas.
Let us write c = 1 + √(3/2) for brevity.



Assume a sequence of n numbers. 
It is possible to partition this sequence in at most c√(n) monotonic subsequences
(increasing or decreasing).


Note that we are not referring to consecutive subsequences.
For example, (5,7,9) is a monotonically increasing subsequence of 
the sequence (5,8,2,7,1,9,6).


We will prove the lemma using induction on n. The result holds for n = 1, 2, 3, 4.
Assume n ≥ 5, and assume that lemma holds for any sequence of length less than n.
Erdős-Szekeres theorem <cit.> 
states that there is a monotonic subsequence whose length is at least
√(n - 1) + 1. 
By removing that monotonic subsequence we are left with a sequence having at most 
n-√(n - 1) - 1 numbers.
By the induction hypothesis this reduced sequence can be 
partitioned in at most c√(n - √(n - 1) - 1) monotonic subsequences.
Thus, it is enough to prove that

    c√(n - √(n - 1) - 1) + 1 ≤ c√(n).


To prove the claim note that

    0    = 2 c(c - 2) - 1 
       ≤√(n - 1)c(c - 2) - 1 
       = c^2√(n - 1) - 2c√(n - 1) - 1 
       ≤ c^2√(n - 1) - 2c√(n - √(n - 1)) - 1 
       = c^2n - c^2(n - √(n - 1)) - 2c√(n - √(n - 1)) - 1 
       = c^2n - 1 + c√(n - √(n - 1))^2.

That is,

    1 + c√(n - √(n - 1))^2 ≤ c^2n,

or

    c√(n - √(n - 1)) + 1 ≤ c√(n).

Since √(n - 1)≤√(n - 1) + 1, the lemma follows.


The next two lemmas show that there exists a directed tree in H with
total weight, say w, less than 2c√(k - 1) times the number of edges in
the solution. This immediately proves Proposition <ref>
since that the total weight of the minimum spanning tree A in is less or equal than w,
and returns a tree with number of edges bounded by the total weight of
A.

The first lemma establishes the bound when the reported nodes are leaves or a root, 
while the second lemma proves the general case 
when the reported nodes can be also internal nodes in the tree.



Let =(, ) be a graph and let  be a set of reported nodes.
Consider a tree = (W, F), with W⊆, whose root and leaves are 
exactly the reported nodes (), with the root having the smallest timestamp.
Then there is a directed tree U = ((), B) 
such that (u, v) ∈ B implies t(u) ≤ t(v),
and

    ∑_(u, v) ∈ B(u, v) ≤ 2 c√( - 1)F.




Write k =, and let u_1, …, u_k - 1 be the leaves in (), ordered
based on a Eulerian tour. Let = u_k be the root of T.

Consider any subsequence of w_1, …, w_ℓ of u_1, …, u_k - 1.
Then

    (, w_1) + ∑_i = 1^ℓ - 1(w_i, w_i + 1) ≤ 2F,

since each (w_i, w_i + 1) is upper-bounded by a path in the Euler tour
and we visit every edge in F at most twice during the tour. We can also reverse the direction
of the tour and obtain

    (, w_ℓ) + ∑_i = 1^ℓ - 1(w_i + 1, w_i) ≤ 2F.

	
To create the tree U, start with a tree containing only the root .
According to Lemma <ref> we can partition u_1, …, u_k - 1 to at
most c√(k - 1) sequences such that the timestamps of nodes in each
subsequence is either increasing or decreasing. Let w_1, …, w_ℓ be such
subsequence. If the time stamps are increasing, then add a path , w_1, …, w_ℓ.
If the time stamps are decreasing, then add a path , w_ℓ, …, w_1.
Repeat this at most c√(k - 1) times.

The total distance weight of each path is 2F and there are at most c√(k - 1)
paths, proving the result.


The second lemma allows reported nodes to be non-leaves. 


Let =(, ) be a graph and let  be a set of reported nodes.
Consider a tree = (W, F), with W⊆, solving .
Then there is a directed tree U = ((), B) such that (u, v) ∈ B implies t(u) ≤ t(v),
and

    ∑_(u, v) ∈ B(u, v) ≤ 2 c√( - 1)F.




We will prove this by induction over V.
If there are no intermediate reported nodes in T, we can apply Lemma <ref> directly.
Assume there is at least one, say v, intermediate reported node.  Let T_1 be the tree corresponding
to the branch rooted at v. Let T_2 be the tree obtained from T by deleting T_1,
but keeping v. Let _1 be the reported nodes in T_2 and let _2 be the reported nodes in T_2.
Apply Lemma <ref> to T_1 and T_2, obtaining U_1 = ((_1), B_1) and U_2 = ((_2), B_2), respectively.
We can join these two trees at v to obtain a joint tree U. This tree respects the time constraints. 
Moreover,

    ∑_(u, v) ∈ B(u, v)     = ∑_(u, v) ∈ B_1(u, v) + ∑_(u, v) ∈ B_2(u, v) 
       ≤ 2 c√(_1 - 1)F_1 + 2 c√(_2 - 1)F_2
       ≤ 2 c√( - 1) (F_1 + F_2) 
        = 2 c√( - 1)F,

proving the result.



The running time of algorithm is as follows. 
Computing shortest-path distances 
to construct the graph H requires time (), 
while finding the minimum directed spanning tree on H requires time (^2).
In the second phase of , 
constructing the Steiner tree requires time (). 
Thus, the overall running time of algorithm is ( + ^2).

Algorithm <ref> contains three stages: finding the shortest paths,
finding minimum spanning tree and steiner tree construction. Note, that we can
merge stage 1 and 2 into one loop of finding the minimum incoming excluding
shortest path for each node. Stage 3 also can be done during this loop. The
resulting Algorithm is Algorithm <ref>.













 §.§ Greedy algorithm


Our second algorithm, , is a simpler variant of . 
avoids the first step of computing 
a minimum spanning tree, 

and instead, it reconstructs the cascade by adding paths to the terminals
in chronological order—i.e., similar to the second phase of . 

Given a terminal node u∈() with timestamp t(u)
and a graph node v∈
we define the extended excluding shortest path 
from v to terminal u 
to be the shortest path from v to u in , 
which may include only terminals w with the same timestamp as u.

The extended excluding shortest path from v to u is denoted by (v,u),
and its length by (v,u).


The algorithm starts by adding to the cascade only the seed node, 
i.e., ({},∅).
Then processes the reported nodes in chronological order.
For each reported nodeu, finds
the shortest extended excluding shortest path (v,u),
over all nodes v that are currently included in the cascade , 
and add this path in .
Pseudocode for is given in Algorithm <ref>.

It is clear that returns a feasible solution.




Additionally, we can show that provides an appro­xi­ma­tion guarantee
for , 
albeit a weaker bound than the one obtained by . 

[t]
	
	
	=(,), ={(u,t)}, root ∈
	Order-respecting 
	rooted in that spans all nodes in ().
	({},∅) 
	u∈() in chronological order
 ties are broken arbitrarily
	


		v min_z∈(z,u) 
		∪(v,u) 
	
		
	




Algorithm yields a -approximation guarantee for the problem.


Consider an input graph =(,), 
a set of reported nodes , and seed . 
Let ^* be the optimal order-respecting tree that covers all reported nodes in (), 
and  be the tree returned by .
Let (^*) be the cost of optimal tree ^*, 
and () the cost of .
Let (, u) be the shortest order-respecting path from to u in .
For each reported node u in () 
we have ((, u))≤(^*). 
In each iteration of we add a path (v,u) with 
(v,u)≤((, u)). 
It follows


    () ≤∑_u∈()(v,u) ≤∑_u∈()((, u)) ≤ (^*).




The running time of is similar to that of :
processing each reported node requires a computation, 
so the overall running time is ().




 §.§ Delayed BFS algorithm


Both previous algorithms, and , 
perform k operations that are equivalent to , 
and thus their running time is ().
In cases that there are many reported nodes, i.e., when  is large, 
algorithms and are not scalable to large graphs.

To address this challenge we propose a third algorithm, ,
which, like , provides a -approximation guarantee,
but is more efficient.
The main idea of is to perform a single starting from the root .
Whenever a terminal  u is encountered,
checks whether all terminals with timestamp smaller than t(u) have been visited.
If they have been visited, the continues.
If not, the “below” node u is delayed 
until all terminals with timestamp smaller than t(u) have been visited.

Pseudocode for is given in Algorithm <ref>.
The variable Q represents the queue 
while D represents a sorted array with the terminals
at which  has been delayed; 
the terminals in D are sorted in chronological order.
The variable t_𝑐𝑢𝑟 keeps the 
smallest timestamp of the terminals that have not been processed yet.
The array c keeps for each timestamp t 
the number of terminals with that timestamp that have not been processed yet.
The counter for c[t] is decreased whenever we delete from D a terminal with timestamp t.
Thus, at each step of the algorithm 
the minimum time t_𝑐𝑢𝑟 can be computed as the smallest timestamp t
for which c[t]≠0 in amortized constant time.

[t]
    
    
    =(,), ={(u,t)}, root 
    Order-respecting 
	rooted in that spans all nodes in ().
	Q 
	D ∅ 
	∅ 
	c[t] v | (v, t) ∈ 
	c[t()]  c[t()] - 1 
	t_𝑐𝑢𝑟mint | c[t] ≠ 0 
	
	Q ≠∅ 
		v top element in Q; delete v from Q 
		v ∉() 
			(v, w) ∈ E with unmarked w 
				add (v, w) to ;
				add w to Q; mark w 
			
		
		
			add v to D 
		
		v in D in chronological order 
			t(v) ≠ t_𝑐𝑢𝑟  
				
			(v, w) ∈ E with unmarked w 
				add (v, w) to ;
				add w to Q; mark w 
			
			c[t(v)]  c[t(v)] - 1 
			t_𝑐𝑢𝑟mint | c[t] ≠ 0 
		
	prune branches from  that do no have terminal leaf 
	 
	


As mentioned before, 
algorithm provides a provable approximation guarantee, 
similar to the one of .


Algorithm yields a -appro­xi­ma­tion guarantee for the problem.



Let  be the tree discovered by the algorithm .
We order the nodes in () based on the visiting by the algorithm, 
() = s_1, …, s_k, 
We write _i for the (sub)tree
that has been formed right after s_i is added to the queue Q.
We use p_i to denote the depth of the tree _i.

Let T^* be the optimal steiner tree, 
and let T^*_i be a subtree of T^* 
containing only branches with leaves from s_1, …, s_i.

We claim that p_i ≤E(T^*_i). 
The proposition follows immediately from this
claim since 

    E(T)≤∑_i = 1^k p_i ≤∑_i = 1^k E(T^*_i)≤ k E(T^*).

To prove the claim, we use induction. The result holds trivially for i = 1.
Assume it holds for i - 1.
Let j be the largest index such that t(s_j) < t(s_i). If no index exist,
then set j = 1. 

Let q be the length of the path in T^* from s_i to the largest ancestor terminal, say
s_ℓ, that is either a root or have a genuinely smaller time stamp.

By induction p_j ≤E(T^*_j), and since s_ℓ∈ V(T^*_j), 
the tree _j can only grow by q in depth before we visit s_i,
that is, p_i ≤ p_j + q ≤E(T^*_j) + q. Note that T^*_j
does not contain the path from s_i to s_ℓ. This implies that E(T^*_j) + q ≤E(T^*_i), proving the claim.



The running time of  is ( + log).
The () part is due to the on the graph 
(the delayed order does not impact the running time)
while the (log) is due to maintaining the arrays D and c.
Thus,  is an algorithm with excellent sca­la­bi­lity 
and can be used for very large graphs.








§ EXPERIMENTAL RESULTS







Datasets:
We experiment on real-world graphs with both simulated and real cascades.
We use the following real-world graphs from SNAP:[http://snap.stanford.edu/data/index.html]
(i)
: email data from an European research institution.
There is an edge (u, v) if person u has sent at least one email at person v.
The graph has 986 nodes and 25 552 edges;
(ii)
: General Relativity and Quantum Cosmology collaboration network from e-print arXiv.
The graph has 4 158 nodes and 13 428 edges; 
(iii) : High Energy Physics collaboration network from the arXiv, 
consisting of 8 638 nodes and 24 827 edges; and
(iv) : “friends lists” from Facebook. 
The graph has 4039 nodes and 88234 edges. 

Cascading models:
We simulate cascades using four types of models. 
(i) susceptible infected ();
(ii) independent cascade ();
(iii) continuous-time diffusion process ()<cit.>;
(iv) shortest path (), in which contagion propagates by shortest paths. 
For , infection probability is set to 0.5.
For , infection time is globally distributed by exponential distribution with β=1.
For , and , we continue the cascade until at least half of the nodes are activated. 
For , activation probability is tuned network-wise to activate on expecation half of the nodes.
For , , and transmission delay is one time unit. 

Real cascades:
We use the dataset.[https://www.isi.edu/ lerman/downloads/digg2009.html]
The underlying graph has 279 631 nodes and 1 548 131 edges.
Each story corresponds to a cascade.
For most cascades the activated nodes do not form a connected component; 
in such cases we extract the largest connected component.

We experimented on 18 large cascades (average size 1 965). 
and 10 small cascades (average size 110).


Methods:
We compare the following four methods:
(i) in Algorithm <ref>;
(ii) in Algorithm <ref>;
(iii) in Algorithm <ref>.
We also consider the standard Steiner-tree problem, 
where no temporal information is used.



The resulting algorithm, , uses the mst-based technique <cit.>.
For all methods, earliest reported activation is selected the root according to Observation <ref>. 

Measures:
To evaluate the performance of each method, we compare:
(i) objective function value defined in Problem <ref>;
(ii) precision and recall of the set of activated nodes inferred by the tree
with respect to the actual activated nodes;
(iii) order accuracy: an edge u → v in the tree is correct if it respects the true infection order, t(u) ≤ t(v). 
Order accuracy is the fraction of correct edges in the predicted tree. 

For all simulated cascades, we experiment with reporting probabilities with exponential increase,
q=0.001 × 2^i | i=0, …, 8.
For real cascades, we experimented with q=0.001 × 2^i | i=1, …, 5.

For simulated cascades, measurements are averaged over 100 runs for each experiment setting, 
while for real cascades, we average over 8 runs. 



Toy example:
In Figure <ref>, we consider a toy graph, 8x8 grid and simulate cascades under IC model with activation probability of 0.5.
Besides the ground truth cascade tree, we show the reconstructed tree by different methods as well as their size and number of violations on node order. 
By definition, both and return order-respecting trees. However, achieves fewer edges.  
Though produces a tree with least edges,
it introduces several order violations, thus the reconstructed tree resembles less the ground-truth than either or . 










Objective function:
Figure <ref> shows the average tree size
with respect to a the fraction of reported nodes. 
For brevity, we show the plots for only two settings here as other settings give similar result.
We observe that produces larger trees than the other methods 
because it does not explicitly minimize tree size.
We expect to give the smallest trees
as it does not impose any ordering constraint. 
However, we observe that  
all methods give comparable sizes.



Precision and recall:
We next demonstrate our methods' adaptability on different graphs and models with respect to node precision and recall.
Figure <ref> varies the graphs while fixing the cascade model, meanwhile Figure <ref> does the other way around.

In both Figure <ref> and Figure <ref>, 
we observe that all four methods achieve node precision larger than 0.8. 

For most settings, node precision is close to 1.
For model in Figure <ref>, precision drops slightly and performs worse than the other three.
Note that even though does not explicitly cope with infection order, it still achieves equivalent performance. 
This demonstrates that the parsimony consideration in is reasonable with respect to achieving high node precision. 

For node recall, we observe the following in both figures. 
First, and ,  node recall grows linearly as proportion of reports.
However, for and , node recall grows slower compared to the other two.
The reason is and are graphs with larger density, in which it generally takes fewer Steiner nodes to construct a Steiner tree. 

Second, tends to achieve higher recall than
the other three 

because it does not explicitly minimize the tree size, therefore it captures more nodes. 
Third, , and tend to have similar recall.










Order accuracy:
Next, we report order accuracy.
In general, , and perform better than under all cascade models and all graphs.
This advantage is demonstrated in Figure <ref>, in which the upper row fixes the cascade model while the lower row fixes the underlying graph. 
This is expected because and explicitly construct tree that respect the infection order.

In addition, methods that models order explicitly improve their order accuracy as proportion of reports increase.
However, this is not always true for .
For example, its order accuracy deteriorates for and under in Figure <ref>. 




Real cascades:
Performance measure on real cascades is given in Figure <ref> for both large and small cascades. 
For most the measures, they demonstrate similar behavior with respect to that on synthetic cascades.
However, one noticeable difference is that node precision drops significantly.
The reasons can be two-fold: 1) the infected nodes are tightly connected with each other as well as other uninfected nodes.
In some cases, the uninfected nodes serve as good Steiner nodes
2) parsimony assumption does not hold for certain real cascades. 



For tree size, both have similar result as simulated cascades. 
For order accuracy, and are better than , while performs the worst. 
For node precision, performs worse than the other three, 
which validates the parsimony consideration in problem formulation.
All methods give similar trend for node recall. 
In other words, 's advantage in recall under simulated cascades is canceled by its lower precision.
In addition, precision and order accuracy is generally higher for all methods on small cascades than large ones.
This is because observation fraction is set higher for experiments on small cascades.
Overall, and are the best, while is more scalable than .






Case study:
To illustrate the strength and weakness of our methodology, we perform case study on one small cascade (114 infections) from dataset. 20% infections are unobserved. 
In Figure <ref>, we show the related subgraph for ease of presentation.
First, manages to produce a small tree, which roughly represents the cascade backbone.
Second, 3 hidden infections are detected, while it also predicts 4 false positives (triangular nodes).
The recall is low because is designed to produce small trees.
False positives are produced because they are tightly connected to the infected nodes thus it's tempting to predict them as infected. We believe it's necessary to leverage other meaningful information such as edge transmission rate to avoid this. 





Scalability:
Last, we evaluate the scalability of . 
We conduct experiments on a 2.5 GHz Intel Xeon machine with 24 GB of memory.

First, we consider running time with respect to size of graphs (E).
We generate synthetic Barabási-Albert graphs with exponentially increasing sizes.
Fraction of reports is fixed to 10%. 
The result is shown on the left-side of Figure <ref>.
On the right side of the figure, we consider running time with respect to the fraction of reports on graph . 
Both plots demonstrate scales roughly linearly with respect to either E or proportion of report.


 



§ CONCLUSION



We introduce a new formulation for the cascade-reconstruction problem, 
based on a variant of the Steiner-tree problem—as 
it is common, the goal is to find a tree that spans all reported active nodes. 
The novelty of our approach is to effectively utilize temporal information of observations, 
namely, activation times.
To account for the available temporal information
we introduce temporal-consistency constraints,
requiring that all paths in the discovered tree 
should preserve the order of the observed timestamps.
For the proposed Steiner-tree problem
we present three approximation algorithms, 
which provide a trade-off between quality guarantee and scalability. 
The most efficient algorithm has linear­ithmic running time, 
and thus, it is able to cope with very large graphs and large number of reported active nodes.

Our works opens interesting directions for future research. 
The main open problem is to close the gap
between the approximation algorithms and inapproximability lower bounds. 
Another interesting direction is to consider 
a different objective function
so as to improve the recall of the reconstructed cascade
without significant harm on precision. 


Acknowledgments.
This work has been supported by the 
Academy of Finland projects “Nestor” (286211),
“Agra” (313927), and “AIDA” (317085), 
and the EC H2020 RIA project “SoBigData” (654024).



IEEEtran








§ PROOFS OF STATEMENTS RELATED TO THE PROBLEM DEFINITION




The optimal solution to the  problem
is a tree rooted at the reported node (u_0, )∈. 
If there is more than one node in the set (), 
any of them can be considered as a root for the optimal tree.



Assume a minimal Steiner tree T, 
rooted in some node .  
Let  be the path from u_0 to . 
The reported nodes in  have all timestamp equal to . 
Let v be a reported node, 
 be a path from v to , and 
' be the path from v to u_0. 
Then ' contains a prefix of  followed by (a part of) . 
Since the reported nodes in  have timestamp equal to , 
it follows that ' is an order-respecting path.
This allows us to re-root the tree from  to u_0
while respecting the order.



Problem is .


The standard problem <cit.>, 
with an input graph =(,) and a set of terminal nodes X, can
be reduced to the problem with the same graph =(,) as the input
and reported nodes ={(x,0)}, for each x∈ X.




§ APPROXIMATION GUARANTEE FOR 



returns an order-respecting Steiner tree, which spans .


First, by the for-loop defined in lines 5–9,
the resulting tree T is a subgraph of , which spans all reported nodes.
For each new reported node u processed in the for-loop,
a new path P is added in the subgraph ,
which contains only one node from , and thus  is indeed a tree.
Moreover, P may contain only the largest time stamps in current .
This makes  an order-respecting Steiner tree.






The algorithm provides
approximation guarantee 2(1+√(3/2))√( - 1) for problem .


To prove this result we first need to prove couple of technical lemmas.
Let us write c = 1 + √(3/2) for brevity.



Assume a sequence of n numbers. 
It is possible to partition this sequence in at most c√(n) monotonic subsequences
(increasing or decreasing).


Note that we are not referring to consecutive subsequences.
For example, (5,7,9) is a monotonically increasing subsequence of 
the sequence (5,8,2,7,1,9,6).


We will prove the lemma using induction on n. The result holds for n = 1, 2, 3, 4.
Assume n ≥ 5, and assume that lemma holds for any sequence of length less than n.
Erdős-Szekeres theorem <cit.> 
states that there is a monotonic subsequence whose length is at least
√(n - 1) + 1. 
By removing that monotonic subsequence we are left with a sequence having at most 
n-√(n - 1) - 1 numbers.
By the induction hypothesis this reduced sequence can be 
partitioned in at most c√(n - √(n - 1) - 1) monotonic subsequences.
Thus, it is enough to prove that

    c√(n - √(n - 1) - 1) + 1 ≤ c√(n).


To prove the claim note that

    0    = 2 c(c - 2) - 1 
       ≤√(n - 1)c(c - 2) - 1 
       = c^2√(n - 1) - 2c√(n - 1) - 1 
       ≤ c^2√(n - 1) - 2c√(n - √(n - 1)) - 1 
       = c^2n - c^2(n - √(n - 1)) - 2c√(n - √(n - 1)) - 1 
       = c^2n - 1 + c√(n - √(n - 1))^2.

That is,

    1 + c√(n - √(n - 1))^2 ≤ c^2n,

or

    c√(n - √(n - 1)) + 1 ≤ c√(n).

Since √(n - 1)≤√(n - 1) + 1, the lemma follows.


The next two lemmas show that there exists a directed tree in H with
total weight, say w, less than 2c√(k - 1) times the number of edges in
the solution. This immediately proves Proposition <ref>
since that the total weight of the minimum spanning tree A in is less or equal than w,
and returns a tree with number of edges bounded by the total weight of
A.

The first lemma establishes the bound when the reported nodes are leaves or a root, 
while the second lemma proves the general case 
when the reported nodes can be also internal nodes in the tree.



Let =(, ) be a graph and let  be a set of reported nodes.
Consider a tree = (W, F), with W⊆, whose root and leaves are 
exactly the reported nodes (), with the root having the smallest timestamp.
Then there is a directed tree U = ((), B) 
such that (u, v) ∈ B implies t(u) ≤ t(v),
and

    ∑_(u, v) ∈ B(u, v) ≤ 2 c√( - 1)F.




Write k =, and let u_1, …, u_k - 1 be the leaves in (), ordered
based on a Eulerian tour. Let = u_k be the root of T.

Consider any subsequence of w_1, …, w_ℓ of u_1, …, u_k - 1.
Then

    (, w_1) + ∑_i = 1^ℓ - 1(w_i, w_i + 1) ≤ 2F,

since each (w_i, w_i + 1) is upper-bounded by a path in the Euler tour
and we visit every edge in F at most twice during the tour. We can also reverse the direction
of the tour and obtain

    (, w_ℓ) + ∑_i = 1^ℓ - 1(w_i + 1, w_i) ≤ 2F.

	
To create the tree U, start with a tree containing only the root .
According to Lemma <ref> we can partition u_1, …, u_k - 1 to at
most c√(k - 1) sequences such that the timestamps of nodes in each
subsequence is either increasing or decreasing. Let w_1, …, w_ℓ be such
subsequence. If the time stamps are increasing, then add a path , w_1, …, w_ℓ.
If the time stamps are decreasing, then add a path , w_ℓ, …, w_1.
Repeat this at most c√(k - 1) times.

The total distance weight of each path is 2F and there are at most c√(k - 1)
paths, proving the result.


The second lemma allows reported nodes to be non-leaves. 


Let =(, ) be a graph and let  be a set of reported nodes.
Consider a tree = (W, F), with W⊆, solving .
Then there is a directed tree U = ((), B) such that (u, v) ∈ B implies t(u) ≤ t(v),
and

    ∑_(u, v) ∈ B(u, v) ≤ 2 c√( - 1)F.




We will prove this by induction over V.
If there are no intermediate reported nodes in T, we can apply Lemma <ref> directly.
Assume there is at least one, say v, intermediate reported node.  Let T_1 be the tree corresponding
to the branch rooted at v. Let T_2 be the tree obtained from T by deleting T_1,
but keeping v. Let _1 be the reported nodes in T_2 and let _2 be the reported nodes in T_2.
Apply Lemma <ref> to T_1 and T_2, obtaining U_1 = ((_1), B_1) and U_2 = ((_2), B_2), respectively.
We can join these two trees at v to obtain a joint tree U. This tree respects the time constraints. 
Moreover,

    ∑_(u, v) ∈ B(u, v)     = ∑_(u, v) ∈ B_1(u, v) + ∑_(u, v) ∈ B_2(u, v) 
       ≤ 2 c√(_1 - 1)F_1 + 2 c√(_2 - 1)F_2
       ≤ 2 c√( - 1) (F_1 + F_2) 
        = 2 c√( - 1)F,

proving the result.





§ APPROXIMATION GUARANTEE OF 






Algorithm yields a -approximation guarantee for the problem.


Consider an input graph =(,), 
a set of reported nodes , and seed . 
Let ^* be the optimal order-respecting tree that covers all reported nodes in (), 
and  be the tree returned by .
Let (^*) be the cost of optimal tree ^*, 
and () the cost of .
Let (, u) be the shortest order-respecting path from to u in .
For each reported node u in () 
we have ((, u))≤(^*). 
In each iteration of we add a path (v,u) with 
(v,u)≤((, u)). 
It follows


    () ≤∑_u∈()(v,u) ≤∑_u∈()((, u)) ≤ (^*).







§ APPROXIMATION GUARANTEE OF 




Algorithm yields a -appro­xi­ma­tion guarantee for the problem.



Let  be the tree discovered by the algorithm .
We order the nodes in () based on the visiting by the algorithm, 
() = s_1, …, s_k, 
We write _i for the (sub)tree
that has been formed right after s_i is added to the queue Q.
We use p_i to denote the depth of the tree _i.

Let T^* be the optimal steiner tree, 
and let T^*_i be a subtree of T^* 
containing only branches with leaves from s_1, …, s_i.

We claim that p_i ≤E(T^*_i). 
The proposition follows immediately from this
claim since 

    E(T)≤∑_i = 1^k p_i ≤∑_i = 1^k E(T^*_i)≤ k E(T^*).

To prove the claim, we use induction. The result holds trivially for i = 1.
Assume it holds for i - 1.
Let j be the largest index such that t(s_j) < t(s_i). If no index exist,
then set j = 1. 

Let q be the length of the path in T^* from s_i to the largest ancestor terminal, say
s_ℓ, that is either a root or have a genuinely smaller time stamp.

By induction p_j ≤E(T^*_j), and since s_ℓ∈ V(T^*_j), 
the tree _j can only grow by q in depth before we visit s_i,
that is, p_i ≤ p_j + q ≤E(T^*_j) + q. Note that T^*_j
does not contain the path from s_i to s_ℓ. This implies that E(T^*_j) + q ≤E(T^*_i), proving the claim.








