The network-untangling problem : from interactions to activity timelines

Show simple item record Rozenshtein, Polina Tatti, Nikolaj Gionis, Aristides 2021-10-02T22:38:07Z 2021-12-18T03:45:45Z 2021
dc.identifier.citation Rozenshtein , P , Tatti , N & Gionis , A 2021 , ' The network-untangling problem : from interactions to activity timelines ' , Data Mining and Knowledge Discovery , vol. 35 , pp. 213–247 .
dc.identifier.other PURE: 150760719
dc.identifier.other PURE UUID: f5a774a1-1f81-4962-bfc0-8a1233712792
dc.identifier.other WOS: 000574786200001
dc.identifier.other ORCID: /0000-0002-2087-5360/work/89117597
dc.description.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) is an element of 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, wepropose 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. en
dc.format.extent 35
dc.language.iso eng
dc.relation.ispartof Data Mining and Knowledge Discovery
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject Temporal networks
dc.subject Complex networks
dc.subject Timeline reconstruction
dc.subject Vertex cover
dc.subject Linear programming
dc.subject 2-SAT
dc.subject ALGORITHMS
dc.subject EVOLUTION
dc.subject 113 Computer and information sciences
dc.title The network-untangling problem : from interactions to activity timelines en
dc.type Article
dc.contributor.organization Department of Computer Science
dc.contributor.organization Helsinki Institute for Information Technology
dc.description.reviewstatus Peer reviewed
dc.relation.issn 1384-5810
dc.rights.accesslevel openAccess
dc.type.version acceptedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
Rozenshtein2021 ... _untanglingProblemFr_1.pdf 2.084Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record