Dynamic hierarchies in temporal directed networks

Nikolaj Tatti*

*Corresponding author for this work

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

Abstract

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. Code related to this paper is available at: https://bitbucket.org/orlyanalytics/temporalagony/.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Proceedings
EditorsFrancesco Bonchi, Michele Berlingerio, Thomas Gärtner, Neil Hurley, Georgiana Ifrim
Pages55-70
Number of pages16
DOIs
Publication statusPublished - 1 Jan 2019
MoE publication typeA4 Article in a conference publication
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - Dublin, Ireland
Duration: 10 Sep 201814 Sep 2018
http://www.ecmlpkdd2018.org/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume11052 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases
Abbreviated titleECML PKDD
CountryIreland
CityDublin
Period10/09/201814/09/2018
Internet address

Fingerprint

Dive into the research topics of 'Dynamic hierarchies in temporal directed networks'. Together they form a unique fingerprint.

Cite this