On the interplay between strong regularity and graph densification

DOI10.1007/978-3-319-58961-9_15MaRDI QIDQ5082152zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 2086426 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Efficient testing of large graphs
• Graph densification
• Hitting and commute times in large random neighborhood graphs
• Lower bounds of tower type for Szemerédi's uniformity lemma
• The Algorithmic Aspects of the Regularity Lemma

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)