  Many real-world phenomena exhibit strong hierarchical structure.
Consequently, in many real-world directed social networks vertices do not play
equal role. Instead, vertices form a hierarchy such that the edges appear
mainly from upper levels to lower levels. Discovering hierarchies from such
graphs is a challenging problem that has gained attention. Formally, given a
directed graph, we want to partition vertices into levels such that ideally
there are only edges from upper levels to lower levels. From computational
point of view, the ideal case is when the underlying directed graph is acyclic.
In such case, we can partition the vertices into a hierarchy such that there
are only edges from upper levels to lower edges. In practice, graphs are rarely
acyclic, hence we need to penalize the edges that violate the hierarchy. One
practical approach is agony, where each violating edge is penalized based on
the severity of the violation. The fastest algorithm for computing agony
requires $O(nm^2)$ time. In the paper we present an algorithm for computing
agony that has better theoretical bound, namely $O(m^2)$. We also show that in
practice the obtained bound is pessimistic and that we can use our algorithm to
compute agony for large datasets. Moreover, our algorithm can be used as
any-time algorithm.
