Volume 26, 2020
|Number of page(s)||25|
|Published online||06 March 2020|
Γ-limit of the cut functional on dense graph sequences
Dipartimento di Matematica, Università di Roma “Tor Vergata”,
2 Dipartimento di Matematica, Università di Torino, Via Carlo Alberto, 10, 10123 Torino, Italy.
3 Dipartimento di Scienze Matematiche “G.L. Lagrange”, Politecnico di Torino, Corso Duca degli Abruzzi, 24, 10129 Torino, Italy.
* Corresponding author: email@example.com
Accepted: 26 April 2019
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 Γ-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.
Mathematics Subject Classification: 49J45 / 49J21 / 05Cxx / 05C63
Key words: Dense graph sequences / large graphs / Γ-convergence / bisection problem / nonlocal variational problems / Young measures
© EDP Sciences, SMAI 2020
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.