A hybrid adjacency and time-based data structure for analysis of temporal networks

DOI10.1007/978-3-030-93409-5_49MaRDI QIDQ2086647zbMATH OpenOpenAlexFDO

Authors Tanner Hilsabeck, Makan Arastuie, Kevin S. Xu

Publication date 25 October 2022

Full work available at URL https://arxiv.org/abs/2206.11444

zbMATH Keywords

adjacency dictionarydynamic graph structuredynamic networkinterval treerelational eventstimestamped network

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

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].

Recommendations

• Using compressed suffix-arrays for a compact representation of temporal-graphs
• Windows into relational events: data structures for contiguous subsequences of edges
• An introduction to temporal graphs: an algorithmic perspective
• Time windowed data structures for graphs
• An introduction to temporal graphs: an algorithmic perspective

Cites work

• A guide to temporal networks
• Incidence matrices and interval graphs
• Introduction to algorithms.
• Multiaspect graphs: algebraic representation and algorithms
• Scan statistics on Enron graphs
• Temporal network theory
• What's in a crowd? Analysis of face-to-face behavioral networks

Cited in

(4)

• Using compressed suffix-arrays for a compact representation of temporal-graphs
• On packing arborescences in temporal networks
• Windows into relational events: data structures for contiguous subsequences of edges
• The shortest-path and bee colony optimization algorithms for traffic control at single intersection with Networkx application

Describes a project that uses

Uses Software

• NetworkX
• SNAP
• GitHub

This page was built for publication: A hybrid adjacency and time-based data structure for analysis of temporal networks

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