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/s41109-022-00489-5
复制
发表时间：
2022-06
影响因子：
2.2
通讯作者：
Tanner Hilsabeck;Makan Arastuie;Kevin S. Xu
中科院分区：
文献类型：
--
作者：
Tanner Hilsabeck;Makan Arastuie;Kevin S. Xu
动态或时态网络可以表示节点之间随时间变化的边。传统的基于邻接的数据结构用于存储网络，如邻接表，设计时没有考虑时间，因此可以快速检索两组节点之间的所有边（基于阳极的切片），但不能快速检索在给定时间间隔内发生的所有边（基于时间的切片）。我们提出了一种用于存储时间网络的混合数据结构，该结构将边缘存储在邻接字典中，从而实现基于节点的快速切片，同时存储在间隔树中，从而实现基于时间的快速切片。我们的混合结构还支持复合切片，其中需要在节点和时间上切片，要么先在节点上切片，要么先在时间上切片。我们进一步提出了一种预测复合切片的方法，该方法试图预测基于节点的复合切片和基于时间的复合切片哪个更有效。我们在许多真实的时态网络数据集上评估了我们的混合数据结构，发现它们比现有的数据结构实现了更快的切片时间，而创建时间和内存使用仅略有增加。
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.