Continuum limit of \(p\)-Laplacian evolution problems on graphs: \(L^q\) graphons and sparse graphs. (English) Zbl 1528.65096
Summary: In this paper we study continuum limits of the discretized \(p\)-Laplacian evolution problem on sparse graphs with homogeneous Neumann boundary conditions. This goes far beyond known results by handling much more general class of kernels, possibly singular, and graph sequences whose limit are the so-called \(L^q\)-graphons. More precisely, we derive a bound on the distance between two continuous-in-time trajectories defined by two different evolution systems (i.e., with different kernels, second member and initial data). Similarly, we provide a bound in the case that one of the trajectories is discrete-in-time and the other is continuous. In turn, these results lead us to establish error estimates of the full discretization of the \(p\)-Laplacian problem on sparse random graphs. In particular, we provide rate of convergence of solutions for the discrete models to the solution of the continuous problem as the number of vertices grows.
MSC:
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
| 05C90 | Applications of graph theory |
| 35R09 | Integro-partial differential equations |
| 45K05 | Integro-partial differential equations |
| 35R02 | PDEs on graphs and networks (ramified or polygonal spaces) |
| 35R60 | PDEs with randomness, stochastic partial differential equations |
References:
| [1] | F. Alvarez and J. Peypouquet, Asymptotic equivalence and Kobayashi-type estimates for nonautonomous monotone operators in Banach spaces. Discrete Contin. Dyn. Syst. 25 (2009) 1109-1128. · Zbl 1177.47060 · doi:10.3934/dcds.2009.25.1109 |
| [2] | F. Andreu, J. Mazón, J. Rossi and J. Toledo, The Neumann problem for nonlocal nonlinear diffusion equations. J. Evol. Equ. 8 (2008) 189-215. · Zbl 1154.35314 · doi:10.1007/s00028-007-0377-9 |
| [3] | F. Andreu, J. Mazón, J. Rossi and J. Toledo. A nonlocal p-laplacian evolution equation with neumann boundary conditions, J. Math. Pures Appl. 90 (2008) 201-227. · Zbl 1165.35322 |
| [4] | F. Andreu-Vaillo, J.M. Mazón, J.D. Rossi and J.J. Toledo-Melero, Nonlocal Diffusion Problems. Vol 165 of Mathematical Surveys and Monographs. American Mathematical Society (2010). · Zbl 1214.45002 · doi:10.1090/surv/165 |
| [5] | N. Ayi and N. Pouradier Duteil, Mean-field and graph limits for collective dynamics models with time-varying weights. J. Differ. Equ. 299 (2021) 65-110. · Zbl 1472.34084 · doi:10.1016/j.jde.2021.07.010 |
| [6] | P.W. Bates and A. Chmaj, An integrodifferential model for phase transitions: stationary solutions in higher space dimensions. J. Stat. Phys. 95 (1999) 1119-1139. · Zbl 0958.82015 · doi:10.1023/A:1004514803625 |
| [7] | P.W. Bates, P.C. Fife, X. Ren and X. Wang, Traveling waves in a convolution model for phase transitions. Arch. Ration. Mech. Anal. 138 (1997) 105-136. · Zbl 0889.45012 · doi:10.1007/s002050050037 |
| [8] | H. Bauschke and P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer (2011). · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7 |
| [9] | P. Bénilan, Solutions intégrales d’éuations d’évolution dans un espace de banach. C. R. Acad. Sci. Paris Ser. A-B 274 (1972) A47-A50. · Zbl 0246.47068 |
| [10] | P. Bénilan and M. Crandall, Completely accretive operators, in , in Semigroup Theory and Evolution Equations. Vol. 135 of Lecture Notes in Pure and Appl. Math. Dekker, New York (1991) 41-75. · Zbl 0895.47036 |
| [11] | U. Biccari, D. Ko and E. Zuazua, Dynamics and control for multi-agent networked systems: a finite-difference approach. Math. Models Methods Appl. Sci. 29 (2019) 755-790. · Zbl 1428.93017 · doi:10.1142/S0218202519400050 |
| [12] | B. Bollobás and O. Riordan, Metrics for sparse graphs, in Surveys in Combinatorics 2009. London Mathematical Society Lecture Note Series, edited by S. Huczynska, J.D. Mitchell and C.M.E. Roney-Dougal. Cambridge University Press, Cambridge (2009) 211-288. · Zbl 1182.05106 · doi:10.1017/CBO9781107325975.009 |
| [13] | C. Borgs, J.T. Chayes, H. Cohn and Y. Zhao, An L^p theory of sparse graph convergence II: LD convergence, quotients and right convergence. Ann. Probab. 46 (2018) 337-396. · Zbl 1386.05099 · doi:10.1214/17-AOP1187 |
| [14] | C. Borgs, J.T. Chayes, H. Cohn and Y. Zhao, An L^p theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. Trans. Amer. Math. Soc. 372 (2019) 3019-3062. · Zbl 1417.05186 · doi:10.1090/tran/7543 |
| [15] | H. Brézis, Opérateurs Maximaux Monotones et semi-groupes de contractions dans les espaces de Hilbert. North Holland, Amsterdam (1973). · Zbl 0252.47055 |
| [16] | T. Bühler and M. Hein, Spectral clustering based on the graph p-Laplacian, in Proceedings of the 26th Annual International Conference on Machine Learning, ICML ‘09. ACM, New York, NY, USA (2009) 81-88. |
| [17] | J. Byström, Sharp constants for some inequalities connected to the p-Laplace operator. J. Inequalities Pure Appl. Math. 6 (2005) 56. · Zbl 1155.26305 |
| [18] | J. Calder, The game theoretic p-laplacian and semi-supervised learning with few labels. Nonlinearity 32 (2018) 301. · Zbl 1408.35048 |
| [19] | C. Carrillo and P. Fife, Spatial effects in discrete generation population models. J. Math. Biol. 50 (2005) 161-188. · Zbl 1080.92054 · doi:10.1007/s00285-004-0284-4 |
| [20] | M.G. Crandall and T.M. Liggett, Generation of semigroups of nonlinear transformations on general banach spaces. Amer. J. Math. 93 (1971) 265-298. · Zbl 0226.47038 · doi:10.2307/2373376 |
| [21] | M.G. Crandall and A. Pazy, Nonlinear evolution equations in banach spaces. Isr. J. Math. 11 (1972) 57-94. · Zbl 0249.34049 · doi:10.1007/BF02761448 |
| [22] | R.A. DeVore and G.G. Lorentz, Constructive Approximation. Vol. 303 of Grundlehren der mathematischen. Springer-Verlag, Berlin Heidelberg (1993). · Zbl 0797.41016 · doi:10.1007/978-3-662-02888-9 |
| [23] | A. El Alaoui, X. Cheng, A. Ramdas, M.J. Wainwright and M.I. Jordan, Asymptotic behavior of ℓ_p-based laplacian regularization in semi-supervised learning, in in 29th Annual Conference on Learning Theory. PMLR (2016) 879-906. |
| [24] | A. Elmoataz, O. Lezoray, S. Bougleux and V.T. Ta, Unifying local and nonlocal processing with partial difference operators on weighted graphs, in International Workshop on Local and Non-Local Approximation in Image Processing. Switzerland (2008) 11-26. · Zbl 1378.94005 |
| [25] | A. Elmoataz, X. Desquesnes, Z. Lakhdari and O. Lézoray, Nonlocal infinity Laplacian equation on graphs with applications in image processing and machine learning. Math. Comput. Simul. 102 (2014) 153-163. · Zbl 1533.05144 · doi:10.1016/j.matcom.2014.01.007 |
| [26] | P. Erdös and A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5 (1960) 17-61. · Zbl 0103.16301 |
| [27] | P. Fife, Some nonclassical trends in parabolic and parabolic-like evolutions, in Trends in Nonlinear Analysis, edited by B Fiedler. Springer-Verlag (2002). · Zbl 1072.35005 |
| [28] | P.C. Fife and X. Wang, A convolution model for interfacial motion: the generation and propagation of internal layers in higher space dimensions. Adv. Differ. Equ. 3 (1998) 85-110. · Zbl 0954.35087 |
| [29] | R. Glowinski and A. Marrocco, Sur l’approximation par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non-linéaires. RAIRO: Anal. Numér. 2 (1975) 41-76. · Zbl 0368.65053 |
| [30] | Y. Hafiene, J. Fadili and A. Elmoataz, Nonlocal p-Laplacian evolution problems on graphs. SIAM J. Numer. Anal. 56 (2018) 1064-1090. · Zbl 1448.65200 · doi:10.1137/17M1123596 |
| [31] | Y. Hafiene, M. Fadili, C. Chesneau and A.E. Moataz, Continuum limit of the nonlocal p-laplacian evolution problem on random in homogeneous graphs. ESAIM: M2AN 54 (2020) 565-589. · Zbl 1442.65212 · doi:10.1051/m2an/2019066 |
| [32] | W. Hoeffding, The Strong Law of Large Numbers for u-Statistics. Institute of Statistics Mimeograph Series 302, North Carolina State University (1961). |
| [33] | D. Kaliuzhnyi-Verbovetskyi and G. Medvedev, The semilinear heat equation on sparse random graphs. SIAM J. Math. Anal. 49 (2017) 1333-1355. · Zbl 1377.34048 · doi:10.1137/16M1075831 |
| [34] | T. Kato, Nonlinear semigroups and evolution equations. J. Math. Soc. Jpn. 19 (1967) 508-520. · Zbl 0163.38303 · doi:10.2969/jmsj/01940508 |
| [35] | B. Kawohl, Variations on the p-Laplacian. Nonlinear Elliptic Part. Differ. Equ. Contemp. Math. 540 (2011) 35-46. · Zbl 1241.35109 · doi:10.1090/conm/540/10657 |
| [36] | Y. Kobayashi, Difference approximation of Cauchy problems for quasi-dissipative operators and generation of nonlinear semigroups. J. Math. Soc. Jpn. 27 (1975) 640-665. · Zbl 0313.34068 · doi:10.2969/jmsj/02740640 |
| [37] | K. Kobayashi, Y. Kobayashi and S. Oharu, Nonlinear evolution operators in Banach spaces. Osaka J. Math. 21 (1984) 281-310. · Zbl 0567.47047 |
| [38] | L. Lovász, Large Networks and Graph Limits. Vol. 60. American Mathematical Society (2012). · Zbl 1292.05001 |
| [39] | G.S. Medvedev, The nonlinear heat equation on dense graphs. SIAM J. Math. Anal. 46 (2014) 2743-2766. · Zbl 1307.34062 · doi:10.1137/130943741 |
| [40] | G.S. Medvedev, The continuum limit of the kuramoto model on sparse random graphs. Commun. Math. Sci. 17 (2019) 883-898. · Zbl 1432.34045 · doi:10.4310/CMS.2019.v17.n4.a1 |
| [41] | R.H. Nochetto and G. Savaré, Nonlinear evolution governed by accretive operators in banach spaces: error control and applications. Math. Models Methods Appl. Sci. 16 (2006) 439-477. · Zbl 1098.65092 · doi:10.1142/S0218202506001224 |
| [42] | W. Rudin, Real and Complex Analysis, 3rd edition. McGraw-Hill (1987). · Zbl 0925.00005 |
| [43] | D. Slepcev and M. Thorpe, Analysis of p-laplacian regularization in semisupervised learning. SIAM J. Math. Anal. 51 (2019) 2085-2120. · Zbl 1422.49020 · doi:10.1137/17M115222X |
| [44] | N.G. Trillos and D. Slepčev, Continuum limit of total variation on point clouds. Arch. Ration. Mech. Anal. 220 (2016) 193-241. · Zbl 1336.68215 · doi:10.1007/s00205-015-0929-z |
| [45] | X. Wang, Metastability and stability of patterns in a convolution model for phase transitions. J. Differ. Equ. 183 (2002) 434-461. · Zbl 1011.35073 · doi:10.1006/jdeq.2001.4129 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
