Graph summarization with quality guarantees

DOI10.1007/S10618-016-0468-8MaRDI QIDQ1741300zbMATH OpenOpenAlexWikidataFDO

Authors Matteo Riondato, David García-Soriano, Francesco Bonchi

Publication date 3 May 2019

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10618-016-0468-8

zbMATH Keywords

approximation algorithmsregularity lemmasummarizationgraph analysiscut-norm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Set-based approximate approach for lossless graph summarization
• Summary data structures for massive data
• Direction matters: on influence-preserving graph summarization and max-cut principle for directed graphs
• Fast algorithms for constructing maximum entropy summary trees
• FLUID: a common model for semantic structural graph summaries based on equivalence relations

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Adaptive Sampling for k-Means Clustering
• An optimal algorithm for finding Frieze-Kannan regular partitions
• Approximating the Cut-Norm via Grothendieck's Inequality
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Bounds for graph regularity and removal lemmas
• Extensions of Lipschitz mappings into a Hilbert space
• Graph clustering
• Graph summarization with quality guarantees
• Large networks and graph limits
• Least squares quantization in PCM
• Local Search Heuristics for k-Median and Facility Location Problems
• Lower bounds of tower type for Szemerédi's uniformity lemma
• NP-hardness of Euclidean sum-of-squares clustering
• On the Complexity of Some Common Geometric Location Problems
• Permuting web and social graphs
• Probability with Martingales
• Quick approximation to matrices and applications
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• The Algorithmic Aspects of the Regularity Lemma
• The Online Median Problem

Cited in

(9)

• Direction matters: on influence-preserving graph summarization and max-cut principle for directed graphs
• Graph Summarization with Latent Variable Probabilistic Models
• Graph summarization with quality guarantees
• Combinatorial trace method for network immunization
• Set-based approximate approach for lossless graph summarization
• An efficient weighted graph aggregation algorithm
• Faster compression methods for a weighted graph using locality sensitive hashing
• Maximum Steiner connected k-core query processing based on graph compression
• Fast algorithms for constructing maximum entropy summary trees

Describes a project that uses

Uses Software

• WebGraph

This page was built for publication: Graph summarization with quality guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741300)