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

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