A sequence of graphs with increasing number of nodes is a dense graph sequence if the number of edges grows as for complete graphs. To each such sequence a function, called graphon, can be associated, which contains information about the asymptotic behavior of the sequence. Here we show that the problem of subdividing a large graph in communities with a minimal amount of cuts can be approached in terms of graphons and the $Gamma$-limit of the cut functional, and discuss the resulting variational principles on some examples. Since the limit cut functional is naturally defined on Young measures, in many instances the partition problem can be expressed in terms of the probability that a node belongs to one of the communities.

Introduction by the Organisers

Paolo Cermelli;DOVETTA, SIMONE
2018-01-01

Abstract

A sequence of graphs with increasing number of nodes is a dense graph sequence if the number of edges grows as for complete graphs. To each such sequence a function, called graphon, can be associated, which contains information about the asymptotic behavior of the sequence. Here we show that the problem of subdividing a large graph in communities with a minimal amount of cuts can be approached in terms of graphons and the $Gamma$-limit of the cut functional, and discuss the resulting variational principles on some examples. Since the limit cut functional is naturally defined on Young measures, in many instances the partition problem can be expressed in terms of the probability that a node belongs to one of the communities.
2018
Emergence of Structures in Particle Systems: Mechanics, Analysis and Computation
European Mathematical Society Publishing House
15
1
3
https://www.mfo.de/document/1844/preliminary_OWR_2018_49.pdf
Dense graph sequences, large graphs, $Gamma$-convergence, bisection problem, nonlocal variational problems, Young measures
Andrea Braides, Paolo Cermelli, Simone Dovetta
File in questo prodotto:
File Dimensione Formato  
preliminary_OWR_2018_49(1).pdf

Accesso aperto

Descrizione: articolo
Tipo di file: PREPRINT (PRIMA BOZZA)
Dimensione 460.48 kB
Formato Adobe PDF
460.48 kB Adobe PDF Visualizza/Apri

I documenti in IRIS 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: https://hdl.handle.net/2318/1705601
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 4
social impact