Time Windowed Data Structures for Graphs

Abstract

We present data structures that can answer time windowed queries for a set of timestamped events in a relational event graph. We study the relational event graph as input to solve (a) time windowed decision problems for monotone graph properties, such as disconnectedness and bipartiteness, and (b) time windowed reporting problems such as reporting the minimum spanning tree, the minimum time interval, and the graph edit distance for obtaining spanning forests. We also present results of window queries for counting subgraphs of a given pattern, such as paths of length 2 (in general graphs) and paths of length 3 (in bipartite graphs), quadrangles and complete subgraphs of a fixed order or of all orders $\ell \geq 3$ (i.e., cliques of size $\ell$). These query results can be used to compute graph parameters that are important for social network analysis, e.g., clustering coefficients, embeddedness and neighborhood overlapping.