In this paper we analyze the practical implications of Szemerédi’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.

On the Interplay between Strong Regularity and Graph Densification

FIORUCCI, MARCO;TORCINOVICH, ALESSANDRO;PELILLO, Marcello
2017

Abstract

In this paper we analyze the practical implications of Szemerédi’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.
Lecture Notes in Computer Science
File in questo prodotto:
File Dimensione Formato  
GbR2017.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Documento in Pre-print
Licenza: Accesso gratuito (solo visione)
Dimensione 934.89 kB
Formato Adobe PDF
934.89 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/3685042
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact