The Network-Untangling Problem: From Interactions to Activity Timelines

Polina Rozenshtein, Nikolaj Tatti, Aristides Gionis

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

2 Citations (Scopus)
230 Downloads (Pure)


In this paper we study a problem of determining when entities are active based on their interactions with each other. More formally, we consider a set of entities V and a sequence of time-stamped edges E among the entities. Each edge (u,v,t)∈E denotes an interaction between entities u and v that takes place at time t. We view this input as a temporal network. We then assume a simple activity model in which each entity is active during a short time interval. An interaction (u, v, t) can be explained if at least one of u or v are active at time t. Our goal is to reconstruct the activity intervals, for all entities in the network, so as to explain the observed interactions. This problem, which we refer to as the network-untangling problem, can be applied to discover timelines of events from complex interactions among entities.

We provide two formulations for the network-untangling problem: (i) minimizing the total interval length over all entities, and (ii) minimizing the maximum interval length. We show that the sum problem is NP-hard, while, surprisingly, the max problem can be solved optimally in linear time, using a mapping to 2-SAT. For the sum problem we provide efficient and effective algorithms based on realistic assumptions. Furthermore, we complement our study with an evaluation on synthetic and real-world datasets, which demonstrates the validity of our concepts and the good performance of our algorithms.
Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2017, Skopje, Macedonia, September 18–22, 2017, Proceedings, Part I
EditorsMichelangelo Ceci, Jaakko Hollmén, Ljupčo Todorovski, Celine Vens, Sašo Džeroski
Place of PublicationCham
Number of pages16
ISBN (Electronic)978-3-319-71249-9
Publication statusPublished - 2017
MoE publication typeA3 Part of a book or another research book
EventEuropean Conference on Principles and Practice of Knowledge Discovery in Databases - Croke Park Conference Centre, Skopje, Macedonia, The Former Yugoslav Republic of
Duration: 18 Sep 201722 Sep 2017
Conference number: 10

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Conference on Principles and Practice of Knowledge Discovery in Databases
Abbreviated titleECML PKDD
Country/TerritoryMacedonia, The Former Yugoslav Republic of


  • Temporal networks
  • Complex networks
  • Timeline reconstruction
  • Vertex cover
  • Linear programming
  • 2-SAT


Dive into the research topics of 'The Network-Untangling Problem: From Interactions to Activity Timelines'. Together they form a unique fingerprint.

Cite this