The network-untangling problem: from interactions to activity timelines

DOI10.1007/S10618-020-00717-5MaRDI QIDQ2659278zbMATH OpenOpenAlexFDO

Authors Polina Rozenshtein, Nikolaj Tatti, Aristides Gionis

Publication date 26 March 2021

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL https://aaltodoc.aalto.fi/handle/123456789/32761

zbMATH Keywords

2-SATcomplex networkslinear programmingtemporal networkstimeline reconstructionvertex cover

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Windows into relational events: data structures for contiguous subsequences of edges
• Connectivity and inference problems for temporal networks
• Social network discovery by mining spatio-temporal events
• Connectivity and inference problems for temporal networks
• Discovering recurring activity in temporal networks

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An introduction to temporal graphs: an algorithmic perspective
• scientific article; zbMATH DE number 3827200 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• On the approximation of curves by line segments using dynamic programming
• Reducibility among combinatorial problems
• Strongly polynomial efficient approximation scheme for segmentation
• The Structure and Function of Complex Networks
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(9)

• Discovering recurring activity in temporal networks
• Disentangling the computational complexity of network untangling
• Untangling temporal graphs of bounded degree
• Timeline cover in temporal graphs: exact and approximation algorithms
• An FPT algorithm for temporal graph untangling
• An FPT algorithm for timeline cover
• Exact and approximation algorithms for covering timeline in temporal graphs
• Partial temporal vertex cover with bounded activity intervals
• Temporal dominating set and temporal vertex cover under the lens of degree restrictions

Describes a project that uses

Uses Software

• TwitterMonitor

This page was built for publication: The network-untangling problem: from interactions to activity timelines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659278)