A sequence of graphs with diverging number of nodes is a dense graph sequence if the number of edges grows approximately 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. Our approach can be used to obtain insights into the bisection problem for large graphs, which is known to be NP-complete.

Γ-limit of the cut functional on dense graph sequences / Braides, Andrea; Cermelli, Paolo; Dovetta, Simone. - In: ESAIM. COCV. - ISSN 1292-8119. - 26:(2020), pp. 1-25. [10.1051/cocv/2019029]

### Γ-limit of the cut functional on dense graph sequences

#### Abstract

A sequence of graphs with diverging number of nodes is a dense graph sequence if the number of edges grows approximately 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. Our approach can be used to obtain insights into the bisection problem for large graphs, which is known to be NP-complete.
##### Scheda breve Scheda completa Scheda completa (DC)
2020
26
1
25
26
https://arxiv.org/abs/1806.03436
Braides, Andrea; Cermelli, Paolo; Dovetta, Simone
File in questo prodotto:
File
2018BCD.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Non specificato
Dimensione 534.17 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/20.500.11767/138230`