The network-untangling problem: from interactions to activity timelines
- PDF / 2,292,871 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 182 Views
The network-untangling problem: from interactions to activity timelines Polina Rozenshtein1,2
· Nikolaj Tatti3,4 · Aristides Gionis2,5
Received: 26 October 2018 / Accepted: 16 September 2020 © The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature 2020
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. Keywords Temporal networks · Complex networks · Timeline reconstruction · Vertex cover · Linear programming · 2- sat
1 Introduction New data abstractions emerging from modern applications require new definitions for data-summarization and synthesis tasks. In particular, for many data that are typically
Responsible editor: Tina Eliassi-Rad, Johannes Fürnkranz. Extended author information available on the last page of the article
123
P. Rozenshtein et al.
modeled as networks, temporal information is nowadays readily available, leading to temporal networks (Holme and Saramäki 2012; Michail 2016). In a temporal network G = (V , E), edges describe interactions over a set of entities V . For each edge (u, v, t) ∈ E, the time of interaction t, between entities u, v ∈ V is also available. In this paper we introduce a new problem formulation for summarizing temporal networks. Network summarization is a well-established problem with applications to data compression, visualization, interactive analysis, and noise elimination. However, temporal network summarization is a rather novel and challenging topic, because of the large variety of temporal network summaries being proposed. An extensive survey f
Data Loading...
