  The outcome of interactions in many real-world systems can be often explained
by a hierarchy between the participants. Discovering hierarchy from a given
directed network can be formulated as follows: partition vertices into levels
such that, ideally, there are only forward edges, that is, edges from upper
levels to lower levels. In practice, the ideal case is impossible, so instead
we minimize some penalty function on the backward edges. One practical option
for such a penalty is agony, where the penalty depends on the severity of the
violation. In this paper we extend the definition of agony to temporal
networks. In this setup we are given a directed network with time stamped
edges, and we allow the rank assignment to vary over time. We propose 2
strategies for controlling the variation of individual ranks. In our first
variant, we penalize the fluctuation of the rankings over time by adding a
penalty directly to the optimization function. In our second variant we allow
the rank change at most once. We show that the first variant can be solved
exactly in polynomial time while the second variant is NP-hard, and in fact
inapproximable. However, we develop an iterative method, where we first fix the
change point and optimize the ranks, and then fix the ranks and optimize the
change points, and reiterate until convergence. We show empirically that the
algorithms are reasonably fast in practice, and that the obtained rankings are
sensible.
