An evolutionary graph framework for analyzing fast-evolving networks

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
University of New Brunswick
Fast-evolving networks by definition are real-world networks that change their structure, becoming denser over time since the number of edges and nodes grows faster, and their properties are also updated frequently. Due to the dynamic nature of these networks, many are too large to deal with and complex to generate new insights into their evolution process. One example includes the Internet of Things, which is expected to generate massive networks of billions of sensor nodes embedded into a smart city infrastructure. This PhD dissertation proposes a Space-Time Varying Graph (STVG) as a conceptual framework for modelling and analyzing fast-evolving networks. The STVG framework aims to model the evolution of a real-world network across varying temporal and spatial resolutions by integrating time-trees, subgraphs and projected graphs. The proposed STVG is developed to explore evolutionary patterns of fast-evolving networks using graph metrics, ad-hoc graph queries and a clustering algorithm. This framework also employs a Whole-graph approach to reduce high storage overhead and computational complexities associated with processing massive real-world networks. Two real-world networks have been used to evaluate the implementation of the STVG framework using a graph database. The overall results demonstrate the application of the STVG framework for capturing operational-level transit performance indicators such as schedule adherence, bus stop activity, and bus route activity ranking. Finally, another application of STVG reveals evolving communities of densely connected traffic accidents over different time resolutions.