Aging data in dynamic graphs: A comparative study

Dynamic graphs are used to represent changing relational data. In order to create a dynamic graph representing relationships or interactions over time, it is necessary to choose a method of adding new data and removing, or otherwise de-emphasizing, past data to decrease its influence. In particular, the question of aging edges is new to dynamic graphs and has not been thoroughly studied. In this work, we address the problem of aging vertices and edges to create a dynamic graph from a stream of temporal data. We provide two new methods, active vertex and active edge, and also evaluate two methods from the literature, sliding window and weight decay. By analyzing various properties of the dynamic graphs created by each aging method, we provide practitioners with quantitative comparisons. We find several interesting similarities and differences. The active vertex and weight decay methods reduce the variability over time of several vertex level measures compared to sliding window and active edge. This means that in practice, active vertex or weight decay may be more useful if graph stability is preferred, while sliding window or active edge may be preferred if the graph should be sensitive to changes in the underlying data stream. Each method also differently affects global measures. The most connected graph is produced by active vertex, while the most disconnected by weight decay. We observe that despite the differences, the graphs produced by each method experience similar types of changes at similar points in time.