The network-untangling problem: from interactions to activity timelines

Polina Rozenshtein*, Nikolaj Tatti, Aristides Gionis

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)
56 Downloads (Pure)

Abstract

In this paper we study a problem of determining when entities are active based on their interactions with each other. 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 at time t. We assume an activity model where each entity is active during at most k time intervals. 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, the network-untangling problem, can be applied to discover event timelines from complex entity interactions. We provide two formulations of the network-untangling problem: (i) minimizing the total interval length over all entities (sum version), and (ii) minimizing the maximum interval length (max version). We study separately the two problems for k= 1 and k> 1 activity intervals per entity. For the case k= 1 , we show that the sum problem is NP-hard, while the max problem can be solved optimally in linear time. For the sum problem we provide efficient algorithms motivated by realistic assumptions. For the case of k> 1 , we show that both formulations are inapproximable. However, we propose efficient algorithms based on alternative optimization. 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
Pages (from-to)213-247
Number of pages35
JournalData Mining and Knowledge Discovery
Volume35
Issue number1
Early online date1 Jan 2020
DOIs
Publication statusPublished - Jan 2021
MoE publication typeA1 Journal article-refereed

Keywords

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

Fingerprint

Dive into the research topics of 'The network-untangling problem: from interactions to activity timelines'. Together they form a unique fingerprint.
  • Active knowledge discovery in graphs

    Gionis, A., Aslay, C., Zhang, G., Ordozgoiti Rubio, B. & Xiao, H.

    01/01/201831/12/2019

    Project: Academy of Finland: Other research funding

  • Adaptive and intelligent data

    Gionis, A., Ordozgoiti Rubio, B., Zhang, G. & Muniyappa, S.

    01/01/201830/06/2022

    Project: Academy of Finland: Other research funding

  • Network structure from group response

    Xiao, H., Gionis, A., Garimella, K., Vitale, F., Parotsidis, N., Zhang, G., Rozenshtein, P., Galbrun, E., Tatti, N., Scepanovic, S., Matakos, A. & Muniyappa, S.

    01/09/201531/08/2019

    Project: Academy of Finland: Other research funding

Cite this