Graph summarization with quality guarantees

DOI10.1007/s10618-016-0468-8zbMath1411.68089OpenAlexW2418808916WikidataQ60113120 ScholiaQ60113120MaRDI QIDQ1741300

David García-Soriano, Matteo Riondato, 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

regularity lemmaapproximation algorithmssummarizationgraph analysiscut-norm

Mathematics Subject Classification ID

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

Related Items (3)

Graph Summarization with Latent Variable Probabilistic Models ⋮ Combinatorial trace method for network immunization ⋮ Graph summarization with quality guarantees

Uses Software

• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph clustering
• NP-hardness of Euclidean sum-of-squares clustering
• Quick approximation to matrices and applications
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Graph summarization with quality guarantees
• Bounds for graph regularity and removal lemmas
• A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
• On the Complexity of Some Common Geometric Location Problems
• Extensions of Lipschitz mappings into a Hilbert space
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Adaptive Sampling for k-Means Clustering
• Probability with Martingales
• The Algorithmic Aspects of the Regularity Lemma
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Local Search Heuristics for k-Median and Facility Location Problems
• The Online Median Problem
• Least squares quantization in PCM
• An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions
• Permuting Web and Social Graphs
• Approximating the Cut-Norm via Grothendieck's Inequality

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