The network-untangling problem: from interactions to activity timelines

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorRozenshtein, Polinaen_US
dc.contributor.authorTatti, Nikolajen_US
dc.contributor.authorGionis, Aristidesen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.contributor.groupauthorAdj. Prof. Gionis Aris groupen
dc.date.accessioned2020-10-16T08:08:26Z
dc.date.available2020-10-16T08:08:26Z
dc.date.embargoinfo:eu-repo/date/embargoEnd/2021-10-03en_US
dc.date.issued2021-01en_US
dc.description| openaire: EC/H2020/654024/EU//SoBigData
dc.description.abstractIn 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.description.versionPeer revieweden
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationRozenshtein, 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-5en
dc.identifier.doi10.1007/s10618-020-00717-5en_US
dc.identifier.issn1384-5810
dc.identifier.otherPURE UUID: 4858b2f8-cc26-4ffa-8afb-680ea744f068en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/4858b2f8-cc26-4ffa-8afb-680ea744f068en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85092012014&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/52206738/SCI_Rozenshtein_The_Network_Untangling.main_1_.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/46958
dc.identifier.urnURN:NBN:fi:aalto-202010165855
dc.language.isoenen
dc.publisherSPRINGER
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/654024/EU//SoBigDataen_US
dc.relation.ispartofseriesData Mining and Knowledge Discoveryen
dc.rightsopenAccessen
dc.subject.keyword2-saten_US
dc.subject.keywordComplex networksen_US
dc.subject.keywordLinear programmingen_US
dc.subject.keywordTemporal networksen_US
dc.subject.keywordTimeline reconstructionen_US
dc.subject.keywordVertex coveren_US
dc.titleThe network-untangling problem: from interactions to activity timelinesen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
Files