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. pp. 136-158. DOI https://doi.org/10.1016/j.tcs.2020.12.019
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. pp. 136-158. DOI https://doi.org/10.1016/j.tcs.2020.12.019
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. pp. 136-158. DOI https://doi.org/10.1016/j.tcs.2020.12.019
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 |
---|---|
Additional Information: | Accepted author manuscript to appear in Theoretical Computer Science |
Uncontrolled Keywords: | Structural graph summary; Semantic graphs; Parameterized formal model |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 30 Mar 2021 11:44 |
Last Modified: | 07 Aug 2024 18:43 |
URI: | http://repository.essex.ac.uk/id/eprint/29774 |
Available files
Filename: 1908.01528v3.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0