Logo des Repositoriums
 
Konferenzbeitrag

Evolution of Degree Metrics in Large Temporal Graphs

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Text/Conference Paper

Zusatzinformation

Datum

2023

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Quelle

Verlag

Gesellschaft für Informatik e.V.

Zusammenfassung

Graph metrics, such as the simple but popular vertex degree and others based on it, are well defined for static graphs. However, adapting static metrics for temporal graphs is still part of current research. In this paper, we propose a set of temporal extensions of four degree-dependent metrics, as well as aggregations like minimum, maximum, and average degree of (i) a vertex over a time interval and (ii) a graph at a specific point in time. We show why using the static degree can lead to wrong assumptions about the relevance of a vertex in a temporal graph and highlight the need to include time as a dimension in the metric. We propose a baseline algorithm to calculate the degree evolution of all vertices in a temporal graph and show its implementation in a distributed in-memory dataflow system. Using real-world and synthetic datasets containing up to 462 million vertices and 1.7 billion edges, we show the scalability of our algorithm on a distributed cluster achieving a speedup of around 12 on 16 machines.

Beschreibung

Rost, Christopher; Gomez, Kevin; Christen, Peter; Rahm, Erhard (2023): Evolution of Degree Metrics in Large Temporal Graphs. BTW 2023. DOI: 10.18420/BTW2023-23. Bonn: Gesellschaft für Informatik e.V.. ISBN: 978-3-88579-725-8. pp. 485-507. Dresden, Germany. 06.-10. März 2023

Zitierform

Tags