Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-11602
For citation please use:
Main Title: Comparing temporal graphs using dynamic time warping
Author(s): Froese, Vincent
Jain, Brijnesh
Niedermeier, Rolf
Renken, Malte
Type: Article
URI: https://depositonce.tu-berlin.de/handle/11303/12802
http://dx.doi.org/10.14279/depositonce-11602
License: https://creativecommons.org/licenses/by/4.0/
Abstract: Within many real-world networks, the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to compare different temporal graphs. To this end, we propose to study dynamic time warping on temporal graphs. We define the dynamic temporal graph warping (dtgw) distance to determine the dissimilarity of two temporal graphs. Our novel measure is flexible and can be applied in various application domains. We show that computing the dtgw-distance is a challenging (in general) NP -hard optimization problem and identify some polynomial-time solvable special cases. Moreover, we develop a quadratic programming formulation and an efficient heuristic. In experiments on real-world data, we show that the heuristic performs very well and that our dtgw-distance performs favorably in de-anonymizing networks compared to other approaches.
Subject(s): heuristic optimization
parameterized algorithms
quadratic programming
temporal graph matching
vertex signatures
Issue Date: 29-Jun-2020
Date Available: 12-Mar-2021
Language Code: en
DDC Class: 004 Datenverarbeitung; Informatik
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2020
Journal Title: Social Network Analysis and Mining
Publisher: SpringerNature
Volume: 10
Issue: 1
Article Number: 50
Publisher DOI: 10.1007/s13278-020-00664-5
EISSN: 1869-5469
ISSN: 1869-5450
TU Affiliation(s): Fak. 4 Elektrotechnik und Informatik » Inst. Softwaretechnik und Theoretische Informatik » FG Algorithmik und Komplexitätstheorie
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons