### Abstract

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 language | English |
---|---|

Title of host publication | Proceedings - IEEE International Conference on Data Mining, ICDM |

Publisher | IEEE |

Pages | 991-996 |

Number of pages | 6 |

Volume | 2016-January |

ISBN (Electronic) | 978-1-4673-9504-5 |

ISBN (Print) | 9781467395038 |

DOIs | |

Publication status | Published - 5 Jan 2016 |

MoE publication type | A4 Article in a conference publication |

Event | IEEE International Conference on Data Mining - Atlantic City, United States Duration: 14 Nov 2015 → 17 Nov 2015 Conference number: 15 |

### Publication series

Name | Proceedings - IEEE International Conference on Data Mining, ICDM |
---|---|

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Number | pp. 51-60 |

ISSN (Print) | 1550-4786 |

### Conference

Conference | IEEE International Conference on Data Mining |
---|---|

Abbreviated title | ICDM |

Country | United States |

City | Atlantic City |

Period | 14/11/2015 → 17/11/2015 |

### Keywords

- Agony
- Capacitated circulation
- Hierarchy discovery

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

## Cite this

*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