Temporal graph algebra

Vera Zaychik Moffitt, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Graph representations underlie many modern computer applications, capturing the structure of such diverse networks as the Internet, personal associations, roads, sensors, and metabolic pathways. While analysis of static graphs is a well-explored field, new emphasis is being placed on understanding and representing the ways in which networks change over time. Current research is delving into graph evolution rate and mechanisms, the impact of specific events on network evolution, and spatial and spatio-temporal patterns. However, systematic support for evolving graph querying and analytics still lacks. Our goal is to fill this gap, giving users an ability to concisely express a wide range of common analysis tasks. In this paper we combine advances in graph databases and in temporal relational databases and propose an evolving graph model, including a representation called TGraph and an algebra called TGA, that adheres to point-based semantics. TGA includes principled temporal generalizations of conventional graph operators, as well as novel operators that support exploratory analysis of evolving graphs at different levels of temporal and structural granularity.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 16th International Symposium on Database Programming Languages, DBPL 2017; Held in conjunction with VLDB 2017
    PublisherAssociation for Computing Machinery
    ISBN (Electronic)9781450353540
    DOIs
    StatePublished - Sep 1 2017
    Event16th International Symposium on Database Programming Languages, DBPL 2017 - Munich, Germany
    Duration: Sep 1 2017 → …

    Publication series

    NameACM International Conference Proceeding Series
    VolumePart F130653

    Other

    Other16th International Symposium on Database Programming Languages, DBPL 2017
    CountryGermany
    CityMunich
    Period9/1/17 → …

    Keywords

    • Analytical Evolutionary Analysis
    • Evolving Graphs
    • Point-based Models

    ASJC Scopus subject areas

    • Software
    • Human-Computer Interaction
    • Computer Vision and Pattern Recognition
    • Computer Networks and Communications

    Fingerprint Dive into the research topics of 'Temporal graph algebra'. Together they form a unique fingerprint.

    Cite this