Research Repository

FLUID: A common model for semantic structural graph summaries based on equivalence relations

Blume, Till and Richerby, David and Scherp, Ansgar (2021) 'FLUID: A common model for semantic structural graph summaries based on equivalence relations.' Theoretical Computer Science, 854. 136 - 158. ISSN 0304-3975

[img] Text
1908.01528v3.pdf - Accepted Version
Restricted to Repository staff only until 14 December 2021.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (993kB) | Request a copy

Abstract

Summarization is a widespread method for handling very large graphs. The task of structural graph summarization is to compute a concise but meaningful synopsis of the key structural information of a graph. As summaries may be used for many different purposes, there is no single concept or model of graph summaries. We have studied existing structural graph summaries for large-scale (semantic) graphs. Despite their different concepts and purposes, we found commonalities in the graph structures they capture. We use these commonalities to provide for the first time a formally defined common model, FLUID (FLexible graph sUmmarIes for Data graphs), that allows us to flexibly define structural graph summaries. FLUID allows graph summaries to be quickly defined, adapted, and compared for different purposes and datasets. To this end, FLUID provides features of structural summarization based on equivalence relations such as distinction of types and properties, direction of edges, bisimulation, and inference. We conduct a detailed complexity analysis of the features provided by FLUID. We show that graph summaries defined with FLUID can be computed in the worst case in time w.r.t. n, the number of edges in the data graph. An empirical analysis of large-scale web graphs with billions of edges indicates a typical running time of . Based on the formal FLUID model, one can quickly define and modify various structural graph summaries from the literature and beyond.

Item Type: Article
Uncontrolled Keywords: Structural graph summary, Semantic graphs, Parameterized formal model
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 30 Mar 2021 11:44
Last Modified: 30 Mar 2021 12:15
URI: http://repository.essex.ac.uk/id/eprint/29774

Actions (login required)

View Item View Item