Learning Centre

The network-untangling problem

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Rozenshtein, Polina
dc.contributor.author Tatti, Nikolaj
dc.contributor.author Gionis, Aristides
dc.date.accessioned 2020-10-16T08:08:26Z
dc.date.available 2020-10-16T08:08:26Z
dc.date.issued 2021-01
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 , no. 1 , pp. 213-247 . https://doi.org/10.1007/s10618-020-00717-5 en
dc.identifier.issn 1384-5810
dc.identifier.other PURE UUID: 4858b2f8-cc26-4ffa-8afb-680ea744f068
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/4858b2f8-cc26-4ffa-8afb-680ea744f068
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85092012014&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/52206738/SCI_Rozenshtein_The_Network_Untangling.main_1_.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/46958
dc.description | openaire: EC/H2020/654024/EU//SoBigData
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) ∈ 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. en
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher SPRINGER
dc.relation info:eu-repo/grantAgreement/EC/H2020/654024/EU//SoBigData
dc.relation.ispartofseries Data Mining and Knowledge Discovery en
dc.rights openAccess en
dc.title The network-untangling problem en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.contributor.department F-Secure Corporation
dc.contributor.department Helsinki Institute for Information Technology (HIIT)
dc.subject.keyword 2-sat
dc.subject.keyword Complex networks
dc.subject.keyword Linear programming
dc.subject.keyword Temporal networks
dc.subject.keyword Timeline reconstruction
dc.subject.keyword Vertex cover
dc.identifier.urn URN:NBN:fi:aalto-202010165855
dc.identifier.doi 10.1007/s10618-020-00717-5
dc.date.embargo info:eu-repo/date/embargoEnd/2021-10-03

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication