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 (a node-based slice) but cannot quickly retrieve all edges that occur within a given time interval (a time-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 enables compound 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.
翻译:动态或时间网络可以代表节点之间的时间变化边缘。 常规的基于对称的数据结构用于储存网络, 如对称列表等的基于对称的数据结构设计时没有纳入时间, 因而可以快速检索两组节点( 节点切片)之间的所有边缘, 但无法快速检索在特定时间间隔内出现的所有边缘( 时间基切片) 。 我们提议了一种混合数据结构来储存时间网络, 将时间网络储存在对称词典中, 允许快速节点切片, 和间距树, 能够快速切片 。 我们的混合结构还允许复合切片, 需要通过切除节点和时间, 或者先切除节点, 然后再切片。 我们进一步提出一种预测化合物切片的方法, 试图预测基于节点或基于时间的复合切片是否更有效 。 我们评估了许多真实时间网络数据集的混合数据结构, 发现它们比现有数据结构的切片时间要快得多, 创造时间和记忆使用方面仅略有增加 。