Hierarchies in directed networks

Nikolaj Tatti*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Interactions in many real-world phenomena can be explained by a stronghierarchical structure. Typically, this structure or ranking is not known, instead we only have observed outcomes of the interactions, and the goal is toinfer the hierarchy from these observations. Discovering a hierarchy in the context of directed networks can be formulated asfollows: given a graph, partition vertices into levels such that, ideally, there are only edges from upper levels to lower levels. The ideal case can onlyhappen if the graph is acyclic. Consequently, in practice we have to introducea penalty function that penalizes edges violating the hierarchy. A practicalvariant for such penalty is agony, where each violating edge is penalized basedon the severity of the violation. Hierarchy minimizing agony can be discoveredin O(m2) time, and much faster in practice. In this paper we introduce severalextensions to agony. We extend the definition for weighted graphs and allow acardinality constraint that limits the number of levels. While, these areconceptually trivial extensions, current algorithms cannot handle them, northey can be easily extended. We provide an exact algorithm of O(m2 log n) time by showing the connection of agony to the capacitated circulation problem. Wealso show that this bound is in fact pessimistic and we can compute agony forlarge datasets. In addition, we show that we can compute agony in polynomialtime for any convex penalty, and, to complete the picture, we show that minimizinghierarchy with any concave penalty is an NP-hard problem.

Original languageEnglish
Title of host publicationProceedings - IEEE International Conference on Data Mining, ICDM
Number of pages6
ISBN (Electronic)978-1-4673-9504-5
ISBN (Print)9781467395038
Publication statusPublished - 5 Jan 2016
MoE publication typeA4 Article in a conference publication
EventIEEE International Conference on Data Mining - Atlantic City, United States
Duration: 14 Nov 201517 Nov 2015
Conference number: 15

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
PublisherInstitute of Electrical and Electronics Engineers Inc.
Numberpp. 51-60
ISSN (Print)1550-4786


ConferenceIEEE International Conference on Data Mining
Abbreviated titleICDM
CountryUnited States
CityAtlantic City


  • Agony
  • Capacitated circulation
  • Hierarchy discovery

Fingerprint Dive into the research topics of 'Hierarchies in directed networks'. Together they form a unique fingerprint.

  • Cite this

    Tatti, N. (2016). Hierarchies in directed networks. In Proceedings - IEEE International Conference on Data Mining, ICDM (Vol. 2016-January, pp. 991-996). [7373424] (Proceedings - IEEE International Conference on Data Mining, ICDM; No. pp. 51-60). IEEE. https://doi.org/10.1109/ICDM.2015.12