Zooming Out on an Evolving Graph

Abstract

An evolving graph maintains the history of changes of graph topology and attribute values over time. Such a graph has a specific temporal and structural resolution. It is often useful to modify this resolution during analysis, for example, to consider communities rather than individual nodes, or to quantify changes at the level of days rather than hours. We propose attribute-based zoom and temporal window-based zoom — two operators that support exploratory analysis of an evolving graph at different levels of resolution. We develop several alternative physical representations of an evolving property graph — a temporal generalization of a property graph — and detail how to implement the proposed zoom operators using dataflow operations. These different physical representations allow us to explore the trade-offs in temporal and structural locality with respect to the performance of the zoom operators. We implement the operators in Apache Spark, evaluate them on real evolving graph datasets, and demonstrate scalability to billion-edge graphs.

Publication
International Conference on Extending Database Technology (EDBT)
Date
Links