A hybrid adjacency and time-based data structure for analysis of temporal networks
A hybrid adjacency and time-based data structure for analysis of temporal networks
复制标题
用于分析时态网络的混合邻接和基于时间的数据结构
DOI：
10.1007/978-3-030-93409-5_49
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Xu, Kevin S.
中科院分区：
文献类型：
--
作者：
Hilsabeck, Tanner;Arastuie, Makan;Xu, Kevin S.
动态或时态网络能够表示节点之间的时变边缘。用于存储网络的传统的基于邻接的数据结构，如邻接列表，被设计为不包含时间，因此可以快速检索两组节点之间的所有边（基于阳极的切片），但不能快速检索在给定时间间隔内出现的所有边（基于时间的切片）。我们提出了一种混合数据结构存储时间网络，存储边缘的邻接字典，使快速基于节点的切片，和一个间隔树，使快速基于时间的切片。我们的混合结构还支持复合切片，其中需要在节点和时间上切片，无论是在节点上切片还是在时间上切片。我们进一步提出了一种预测复合切片的方法，该方法试图预测基于节点或基于时间的复合切片是否更有效。我们评估我们的混合数据结构上的许多真实的时间网络数据集，发现他们实现了更快的切片时间比现有的数据结构，只有适度增加创建时间和内存使用。
Dynamic or temporal networks enable representation of time-varying edges between nodes. Conventional adjacency-based data structures used for storing networks such as adjacency lists were designed without incorporating time and can thus quickly retrieve all edges between two sets of nodes (anode-based slice) but cannot quickly retrieve all edges that occur within a given time interval (atime-based slice). We propose a hybrid data structure for storing temporal networks that stores edges in both an adjacency dictionary, enabling rapid node-based slices, and an interval tree, enabling rapid time-based slices. Our hybrid structure also enablescompound slices, where one needs to slice both over nodes and time, either by slicing first over nodes or slicing first over time. We further propose an approach for predictive compound slicing, which attempts to predict whether a node-based or time-based compound slice is more efficient. We evaluate our hybrid data structure on many real temporal network data sets and find that they achieve much faster slice times than existing data structures with only a modest increase in creation time and memory usage.