A hybrid adjacency and time-based data structure for analysis of temporal networks
type: Item
instance of: scholarly article
title: A hybrid adjacency and time-based data structure for analysis of temporal networks
DOI: 10.1007/978-3-030-93409-5_49
author: Tanner Hilsabeck
author: Makan Arastuie
author: Kevin S. Xu
publication date: 2022-10-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/2206.11444
review text: In this paper, a hybrid data structure for storing temporal networks is investigated, in view of rapidly retrieving edges that meet specified criteria, which are called \textit{slicing}. In the proposed approach edges are timestamped, and stored in both an adjacency dictionary, and an interval tree. The adjacency dictionary is exploited to perform rapid node-based slices, which retrieve all edges at any time between two node sets. The interval tree structure stores edges using the edge time duration as the key, and is exploited to perform rapid time-based slices, which retrieve all edges between any two nodes with times that overlap a given search interval. Compound slices are also included in the proposed method. These combine both the two previous criteria, so retrieving all edges between two node sets with times that overlap a given search interval. The model is then tested on different data sets, ranging from networks having very few nodes but lots of short temporal edges, to networks consisting of a huge number of nodes, and extremely long duration temporal edges. It turns out that it achieves much faster slice times than existing structures, with only a modest increase in data sets creation time and in the memory usage. For the entire collection see [Zbl 1492.94005].
reviewed by: Paolo Dulio
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7607304
zbMATH Keywords: dynamic network
zbMATH Keywords: adjacency dictionary
zbMATH Keywords: interval tree
zbMATH Keywords: dynamic graph structure
zbMATH Keywords: relational events
zbMATH Keywords: timestamped network
describes a project that uses: NetworkX
describes a project that uses: SNAP
describes a project that uses: GitHub
MaRDI profile type: Publication
OpenAlex ID: W4205535261
cites work: Q3651735
cites work: Incidence matrices and interval graphs
cites work: Temporal Network Theory
cites work: What's in a crowd? Analysis of face-to-face behavioral networks
cites work: A guide to temporal networks
cites work: Scan statistics on Enron graphs
cites work: Multiaspect graphs: algebraic representation and algorithms
description: scientific article; zbMATH DE number 7607304