The Network-Untangling Problem: From Interactions to Activity Timelines

 |  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.contributor.editor Ceci, Michelangelo
dc.contributor.editor Hollmén, Jaakko
dc.contributor.editor Todorovski, Ljupčo
dc.contributor.editor Vens, Celine
dc.contributor.editor Džeroski, Sašo
dc.date.accessioned 2018-08-01T12:42:22Z
dc.date.available 2018-08-01T12:42:22Z
dc.date.issued 2017
dc.identifier.citation Rozenshtein , P , Tatti , N & Gionis , A 2017 , The Network-Untangling Problem: From Interactions to Activity Timelines . in M Ceci , J Hollmén , L Todorovski , C Vens & S Džeroski (eds) , Machine Learning and Knowledge Discovery in Databases : European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18–22, 2017, Proceedings, Part I . vol. 1 , Lecture Notes in Computer Science , vol. 10534 , Springer International Publishing AG , Cham , pp. 701-716 , European Conference on Machine Learning and Knowledge Discovery in Databases , Skopje , Macedonia, The Former Yugoslav Republic of , 18/09/2017 . DOI: 10.1007/978-3-319-71249-9_42 en
dc.identifier.isbn 978-3-319-71248-2
dc.identifier.isbn 978-3-319-71249-9
dc.identifier.issn 0302-9743
dc.identifier.issn 1611-3349
dc.identifier.other PURE UUID: 535bd451-a164-4842-9c3d-40a8bf1a5190
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/the-networkuntangling-problem-from-interactions-to-activity-timelines(535bd451-a164-4842-9c3d-40a8bf1a5190).html
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/26625818/netuntangle.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/32761
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. 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 thatthe 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. en
dc.format.extent 16
dc.format.extent 701-716
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.ispartof European Conference on Machine Learning and Knowledge Discovery in Databases en
dc.relation.ispartofseries Machine Learning and Knowledge Discovery in Databases en
dc.relation.ispartofseries Volume 1 en
dc.relation.ispartofseries Lecture Notes in Computer Science en
dc.relation.ispartofseries Volume 10534 en
dc.rights openAccess en
dc.subject.other 113 Computer and information sciences en
dc.title The Network-Untangling Problem: From Interactions to Activity Timelines en
dc.type A3 Kirjan tai muun kokoomateoksen osa fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.subject.keyword Temporal networks
dc.subject.keyword Complex networks
dc.subject.keyword Timeline reconstruction
dc.subject.keyword Vertex cover
dc.subject.keyword Linear programming
dc.subject.keyword 2-SAT
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201808014161
dc.identifier.doi 10.1007/978-3-319-71249-9_42
dc.type.version acceptedVersion


Files in this item

Files Size Format View

There are no 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

Browse

My Account