论文标题
用于分析时间网络的混合邻接和基于时间的数据结构
A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks
论文作者
论文摘要
动态或时间网络可以表示节点之间的时变边缘。设计用于存储网络（例如邻接列表）的常规基于邻接的数据结构是设计的，而无需合并时间，因此可以快速检索两个节点之间的所有边缘（基于节点的切片），但无法快速检索在给定时间间隔内发生的所有边缘（一个基于时间的切片）。我们提出了一种混合数据结构，用于存储时间网络，该时间网络将边缘存储在相邻字典中，启用基于快速节点的切片和间隔树，从而实现快速基于时间的切片。我们的混合结构还可以实现复合切片，其中人们需要首先切成节点或随着时间的推移将其切成节点和时间。我们进一步提出了一种预测化合物切片的方法，该方法试图预测基于节点的或基于时间的化合物切片更有效。我们在许多真实的时间网络数据集上评估了混合数据结构，发现它们的切片时间比现有数据结构更快，而创建时间和内存使用率仅适度增加。
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.
