On the interplay between strong regularity and graph densification

DOI10.1007/978-3-319-58961-9_15zbMATH Open1489.68191arXiv1703.07107OpenAlexW2604396438MaRDI QIDQ5082152FDOQ5082152

Authors: Marco Fiorucci, Alessandro Torcinovich, Manuel Curado, F. Escolano, Marcello Pelillo 

Publication date: 15 June 2022

Published in: Graph-Based Representations in Pattern Recognition (Search for Journal in Brave)

Abstract: In this paper we analyze the practical implications of Szemer'edi's regularity lemma in the preservation of metric information contained in large graphs. To this end, we present a heuristic algorithm to find regular partitions. Our experiments show that this method is quite robust to the natural sparsification of proximity graphs. In addition, this robustness can be enforced by graph densification.

Full work available at URL: https://arxiv.org/abs/1703.07107

Recommendations

• Szemerédi's regularity Lemma for matrices and sparse graphs
• The Algorithmic Aspects of the Regularity Lemma
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Can a graph have distinct regular partitions?
• Holes in graphs

zbMATH Keywords

graph algorithmsregular partitioncommute timegraph densification

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Density (toughness, etc.) (05C42)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient testing of large graphs
• Lower bounds of tower type for Szemerédi's uniformity lemma
• The Algorithmic Aspects of the Regularity Lemma
• Title not available (Why is that?)
• Hitting and commute times in large random neighborhood graphs
• Graph densification

Cited In (2)

• On dense strongly \(\mathbb{Z}_{2 s + 1}\)-connected graphs
• Graph densification

This page was built for publication: On the interplay between strong regularity and graph densification

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