Projects per year
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 timestamped 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 networkuntangling problem, can be applied to discover event timelines from complex entity interactions. We provide two formulations of the networkuntangling 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 NPhard, 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 realworld datasets, which demonstrates the validity of our concepts and the good performance of our algorithms.
Original language  English 

Pages (fromto)  213247 
Number of pages  35 
Journal  Data Mining and Knowledge Discovery 
Volume  35 
Issue number  1 
Early online date  1 Jan 2020 
DOIs  
Publication status  Published  Jan 2021 
MoE publication type  A1 Journal articlerefereed 
Keywords
 2sat
 Complex networks
 Linear programming
 Temporal networks
 Timeline reconstruction
 Vertex cover
Fingerprint
Dive into the research topics of 'The networkuntangling problem: from interactions to activity timelines'. Together they form a unique fingerprint.Projects
 3 Finished

AIDA/Gionis
Gionis, A., Ordozgoiti Rubio, B., Zhang, G. & Muniyappa, S.
01/01/2018 → 30/06/2022
Project: Academy of Finland: Other research funding

AGRA/Gionis
Gionis, A., Aslay, C., Zhang, G., Ordozgoiti Rubio, B. & Xiao, H.
01/01/2018 → 31/12/2019
Project: Academy of Finland: Other research funding

NESTOR/Gionis
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/2015 → 31/08/2019
Project: Academy of Finland: Other research funding