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.
Mots-clés : Dense graph sequences, large graphs, Γ-convergence, bisection problem, nonlocal variational problems, Young measures
@article{COCV_2020__26_1_A26_0,
author = {Braides, Andrea and Cermelli, Paolo and Dovetta, Simone},
title = {\ensuremath{\Gamma}-limit of the cut functional on dense graph sequences},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {26},
year = {2020},
doi = {10.1051/cocv/2019029},
mrnumber = {4072631},
zbl = {1439.05068},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/cocv/2019029/}
}
TY - JOUR AU - Braides, Andrea AU - Cermelli, Paolo AU - Dovetta, Simone TI - Γ-limit of the cut functional on dense graph sequences JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2020 VL - 26 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/cocv/2019029/ DO - 10.1051/cocv/2019029 LA - en ID - COCV_2020__26_1_A26_0 ER -
%0 Journal Article %A Braides, Andrea %A Cermelli, Paolo %A Dovetta, Simone %T Γ-limit of the cut functional on dense graph sequences %J ESAIM: Control, Optimisation and Calculus of Variations %D 2020 %V 26 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/cocv/2019029/ %R 10.1051/cocv/2019029 %G en %F COCV_2020__26_1_A26_0
Braides, Andrea; Cermelli, Paolo; Dovetta, Simone. Γ-limit of the cut functional on dense graph sequences. ESAIM: Control, Optimisation and Calculus of Variations, Tome 26 (2020), article no. 26. doi : 10.1051/cocv/2019029. http://archive.numdam.org/articles/10.1051/cocv/2019029/
[1] and , Statistical mechanics of complex networks. Rev. Mod. Phys. 47 (2002) 47–97. | DOI | MR | Zbl
[2] and , Local and non local continuum limits of Ising type energies for spin systems. SIAM J. Math. Anal. 48 (2016) 895–931. | DOI | MR | Zbl
[3] , and , Phase and anti-phase boundaries in binary discrete systems: a variational viewpoint. Netw. Heterog. Media 1 (2006) 85–107. | DOI | MR | Zbl
[4] , and , Variational description of bulk energies for bounded and unbounded spin systems. Nonlinearity 21 (2008) 1881–1910. | DOI | MR | Zbl
[5] , New fundamentals of Young measure convergence. Vol. 410 of Calculus of Variations and Differential Equations, edited by , and . Chapman and Hall/CRC Research Notes in Mathematics (1999) 24–48. | MR | Zbl
[6] , Lectures on Young measure theory and its applications in economics. Workshop on Measure Theory and Real Analysis (Grado, 1997). Rendiconti dell’Istituto di Matematica dell’Università di Trieste 31 (suppl. 1) (2000) 1–69. | MR | Zbl
[7] , On ws-convergence of product measures. Math. Oper. Res. 26 (2001) 494–518. | DOI | MR | Zbl
[8] , A version of the fundamental theorem for Young measures, in PDEs and continuum models of phase transitions, in Vol. 344 of Lecture Notes in Physics (1989) 207–215. | DOI | MR | Zbl
[9] and , Lower semicontinuity and relaxation via Young measures for nonlocal variational problems and applications to peridynamics. SIAM J. Math. Anal. 50 (2018) 779–809. | DOI | MR | Zbl
[10] and , Recurrence of distributional limits of finite planar graphs. Electr. J. Probab. 6 (2001) 1–13. | MR | Zbl
[11] and , Γ-convergence of Ginzburg-Landau graph functionals. Adv. Differ. Equ. 17 (2012) 1115–1180. | MR | Zbl
[12] , , , and , Counting graph homomorphisms. Top. Discr. Math. Ser. Algor. Combin. 26 (2006) 315–371. | DOI | MR | Zbl
[13] , , , and , Convergent sequences of dense graphs I. Subgraph frequencies, metric properties and testing. Adv. Math. 219 (2008) 1801–1851. | DOI | MR | Zbl
[14] , and , Moments of two-variable functions and the uniqueness of graph limits. Geometr. Funct. Anal. 19 (2010) 1597–1619. | DOI | MR | Zbl
[15] , , , and , Limits of randomly grown graph sequences. Eur. J. Combinat. 32 (2011) 985–999. | DOI | MR | Zbl
[16] , , , and , Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. Math. 176 (2012) 151–219. | DOI | MR | Zbl
[17] , , and , Non-Local functionals for imaging, in Fixed-Point Algorithms for Inverse Problemsin Science and Engineering, edited by , , , , and . Springer, New York (2011). | DOI | MR | Zbl
[18] , Γ-convergence for beginners, Oxford University Press, Oxford (2002). | DOI | MR | Zbl
[19] , A handbook of Γ-convergence, Vol. 3 of Handbook of Differential Equations: Stationary Partial Differential Equations (2006) 101–213. | Zbl
[20] , , and , Asymptotic analysis of a ferromagnetic Ising system with “diffuse” interfacial energy. Ann. Matemat. Pura Appl. 197 (2018) 583–604. | DOI | MR | Zbl
[21] and , From discrete to continuous variational problems: an introduction, in Topics in concentration phenomena and problem with multiple scales, edited by and . Springer (2006). | DOI | MR | Zbl
[22] and , Continuum limits of discrete systems without convexity hypothesis. Math. Mech. Solids 7 (2002) 41–66. | DOI | MR | Zbl
[23] , Sequential Lower Semi-Continuity of Non-Local Functionals. Preprint [math.FA] (2011). | arXiv
[24] and , Quick approximation to matrices and applications. Combinatorica 19 (1999) 175–220. | DOI | MR | Zbl
[25] , and , Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237–267. | DOI | MR | Zbl
[26] , Graphons, cut norm and distance, couplings and rearrangements. Vol. 4 of New York J. Math. Monogr. (2013). | MR | Zbl
[27] , Vol. 60 of Large networks and graph limits. American Mathematical Society Colloquium Publications (2012). | MR | Zbl
[28] and , Limits of dense graph sequences. J. Combinat. Theory Ser. B 96 (2006) 933–957. | DOI | MR | Zbl
[29] and , Szemerédi’s lemma for the analyst. Geometr. Funct. Anal. 17 (2007) 252–270. | MR | Zbl
[30] , Nonlocal variational principles. Nonlin. Anal. Theory Methods Appl. 29 (1997) 1379–1392. | DOI | MR | Zbl
[31] , Weak lower semicontinuity and relaxation for a class of non-local functionals. Revista Matemática Complutense 29 (2016) 485–495. | DOI | MR | Zbl
[32] and , Tightness, integral equicontinuity and compactness for evolution problems in Banach spaces. Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, Ser. 5 2 (2003) 395–431. | Numdam | MR | Zbl
[33] and , Continuum limits of total variation on point clouds. Arch. Ratl. Mech. Anal. 220 (2016) 193–241. | DOI | MR | Zbl
[34] , A course on Young measures. Rendiconti dell’Istituto di Matematica dell’Universitá di Trieste 26 (1994) 349–394. | MR | Zbl
Cité par Sources :
