Probability-graphons: Limits of large dense weighted graphs
Abraham, Romain1; Delmas, Jean-François2; Weibel, Julien3
1 Institut Denis Poisson Université d’Orléans, Université de Tours, CNRS France
2 CERMICS Ecole des Ponts France
3 Institut Denis Poisson Université d’Orléans, Université de Tours, CNRS France and CERMICS Ecole des Ponts France
Innovations in Graph Theory, Volume 2 (2025), pp. 25-117.

We introduce probability-graphons which are probability kernels that generalize graphons to the case of weighted graphs. Probability-graphons appear as the limit objects to study sequences of large weighted graphs whose distribution of subgraph sampling converge. The edge-weights are taken from a general Polish space, which also covers the case of decorated graphs. Here, graphs can be either directed or undirected. Starting from a distance $d_\mathrm{m}$ inducing the weak topology on measures, we define a cut distance on probability-graphons, making it a Polish space, and study the properties of this cut distance. In particular, we exhibit a tightness criterion for probability-graphons related to relative compactness in the cut distance. We also prove that under some conditions on the distance $d_\mathrm{m}$, which are satisfied for some well-know distances like the Lévy–Prokhorov distance, and the Fortet–Mourier and Kantorovitch–Rubinshtein norms, the topology induced by the cut distance on the space of probability-graphons is independent from the choice of $d_\mathrm{m}$. Eventually, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.7
Classification: 05C80, 60B10
Keywords: random graphs, stochastic networks, graphons, probability-graphons, dense graph limits, weighted graphs, decorated graphs

Abraham, Romain 1; Delmas, Jean-François 2; Weibel, Julien 3

1 Institut Denis Poisson Université d’Orléans, Université de Tours, CNRS France
2 CERMICS Ecole des Ponts France
3 Institut Denis Poisson Université d’Orléans, Université de Tours, CNRS France and CERMICS Ecole des Ponts France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2025__2__25_0,
     author = {Abraham, Romain and Delmas, Jean-Fran\c{c}ois and Weibel, Julien},
     title = {Probability-graphons: {Limits} of large dense weighted graphs},
     journal = {Innovations in Graph Theory},
     pages = {25--117},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     year = {2025},
     doi = {10.5802/igt.7},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.7/}
}
TY  - JOUR
AU  - Abraham, Romain
AU  - Delmas, Jean-François
AU  - Weibel, Julien
TI  - Probability-graphons: Limits of large dense weighted graphs
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 25
EP  - 117
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.7/
DO  - 10.5802/igt.7
LA  - en
ID  - IGT_2025__2__25_0
ER  - 
%0 Journal Article
%A Abraham, Romain
%A Delmas, Jean-François
%A Weibel, Julien
%T Probability-graphons: Limits of large dense weighted graphs
%J Innovations in Graph Theory
%D 2025
%P 25-117
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.7/
%R 10.5802/igt.7
%G en
%F IGT_2025__2__25_0
Abraham, Romain; Delmas, Jean-François; Weibel, Julien. Probability-graphons: Limits of large dense weighted graphs. Innovations in Graph Theory, Volume 2 (2025), pp. 25-117. doi : 10.5802/igt.7. https://igt.centre-mersenne.org/articles/10.5802/igt.7/

[1] Albert, Réka; Albert, István; Nakarado, Gary L. Structural Vulnerability of the North American Power Grid, Physical Review E, Volume 69 (2004) no. 2, Paper no. 025103 (Accessed 2023-09-26) | DOI

[2] Albert, Réka; Barabási, Albert-László Statistical Mechanics of Complex Networks, Reviews of Modern Physics, Volume 74 (2002) no. 1, pp. 47-97 (Accessed 2023-09-26) | DOI | MR | Zbl

[3] Aletti, Giacomo; Naldi, Giovanni Opinion Dynamics on Graphon: The Piecewise Constant Case, Applied Mathematics Letters, Volume 133 (2022), Paper no. 108227 (Accessed 2023-12-21) | DOI | MR | Zbl

[4] Alonso, L; Méndez-Bermúdez, J A; González-Meléndrez, A; Moreno, Yamir Weighted Random-Geometric and Random-Rectangular Graphs: Spectral and Eigenfunction Properties of the Adjacency Matrix, Journal of Complex Networks, Volume 6 (2018) no. 5, pp. 753-766 (Accessed 2023-12-21) | DOI | MR

[5] Amini, Hamed; Draief, Moez; Lelarge, Marc Flooding in Weighted Sparse Random Graphs, SIAM Journal on Discrete Mathematics, Volume 27 (2013) no. 1, pp. 1-26 (Accessed 2023-09-22) | DOI | MR | Zbl

[6] Amini, Hamed; Lelarge, Marc The Diameter of Weighted Random Graphs, The Annals of Applied Probability, Volume 25 (2015) no. 3, pp. 1686-1727 (Accessed 2023-09-19) | DOI | MR | Zbl

[7] Archer, Eleanor; Nachmias, Asaf; Shalev, Matan The GHP Scaling Limit of Uniform Spanning Trees in High Dimensions, Communications in Mathematical Physics, Volume 405 (2024) no. 3, Paper no. 73 (Accessed 2024-07-01) | DOI | MR | Zbl

[8] Athreya, Siva; Pal, Soumik; Somani, Raghav; Tripathi, Raghavendra Path Convergence of Markov Chains on Large Graphs, 2023 (Accessed 2025-01-21) | arXiv | DOI

[9] Ayi, Nathalie; Duteil, Nastassia Pouradier Graph Limit for Interacting Particle Systems on Weighted Random Graphs, 2023 (Accessed 2023-09-13) | arXiv

[10] Bhamidi, Shankar; Van Der Hofstad, Remco; Hooghiemstra, Gerard First Passage Percolation on Random Graphs with Finite Mean Degrees, The Annals of Applied Probability, Volume 20 (2010) no. 5, pp. 1907-1965 (Accessed 2023-09-22) | DOI | MR | Zbl

[11] Billingsley, Patrick Convergence of Probability Measures, Wiley, New York, 1999 | DOI | MR

[12] Bogachev, Vladimir I. Measure Theory Vol. 1, 1, Springer, Berlin ; New York, 2007 | DOI | MR

[13] Bogachev, Vladimir I. Measure Theory Vol. 2, 2, Springer, Berlin ; New York, 2007 | DOI | MR

[14] Bogachev, Vladimir I. Weak Convergence of Measures, Mathematical Surveys and Monographs, American Mathematical Society, Providence, Rhode Island, 2018 no. volume 234 | DOI | MR

[15] Bollobás, Béla; Janson, Svante; Riordan, Oliver The Cut Metric, Random Graphs, and Branching Processes, Journal of Statistical Physics, Volume 140 (2010) no. 2, pp. 289-335 (Accessed 2023-09-18) | DOI | MR | Zbl

[16] Borgs, C.; Chayes, J.T.; Lovász, L.; Sós, V.T.; Vesztergombi, K. Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing, Advances in Mathematics, Volume 219 (2008) no. 6, pp. 1801-1851 (Accessed 2023-09-18) | DOI | MR | Zbl

[17] Borgs, Christian; Chayes, Jennifer Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks, Proceedings of the 2017 ACM Conference on Economics and Computation, ACM, Cambridge Massachusetts USA (2017), pp. 665-672 (Accessed 2023-12-21) | DOI

[18] Borgs, Christian; Chayes, Jennifer; Lovász, László; Sós, Vera; Vesztergombi, Katalin Convergent Sequences of Dense Graphs II. Multiway Cuts and Statistical Physics, Annals of Mathematics, Volume 176 (2012) no. 1, pp. 151-219 (Accessed 2023-09-18) | DOI | MR | Zbl

[19] Handbook of Graphs and Networks: From the Genome to the Internet (Bornholdt, Stefan; Schuster, Hans Georg, eds.), Wiley, 2002 (Accessed 2023-09-26) | DOI | MR

[20] Delmas, Jean-François; Dronnier, Dylan; Zitt, Pierre-André An Infinite-Dimensional Metapopulation SIS Model, Journal of Differential Equations, Volume 313 (2022), pp. 1-53 (Accessed 2023-12-21) | DOI | MR | Zbl

[21] Draief, Moez; Massoulié, Laurent Epidemics and Rumours in Complex Networks, London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge ; New York, 2010 no. 369 | MR

[22] Dubins, Lester; Freedman, David Measurable Sets of Measures, Pacific Journal of Mathematics, Volume 14 (1964) no. 4, pp. 1211-1222 | DOI | MR | Zbl

[23] Engelking, Ryszard General topology, Sigma series in pure mathematics, Heldermann, Berlin, 1989 no. 6

[24] Ethier, Stewart N; Kurtz, Thomas G Markov processes: characterization and convergence, 282, John Wiley & Sons, 2009 | MR

[25] Falgas-Ravry, Victor; O’Connell, Kelly; Strömberg, Johanna; Uzzell, Andrew Multicolour Containers and the Entropy of Decorated Graph Limits, 2016 (Accessed 2023-10-24) | arXiv

[26] Freedman, Michael; Lovász, László; Schrijver, Alexander Reflection Positivity, Rank Connectivity, and Homomorphism of Graphs, Journal of the American Mathematical Society, Volume 20 (2006) no. 1, pp. 37-51 (Accessed 2023-09-18) | DOI | MR

[27] Frieze, Alan; Kannan, Ravi Quick Approximation to Matrices and Applications, Combinatorica, Volume 19 (1999) no. 2, pp. 175-220 (Accessed 2024-06-27) | DOI | MR | Zbl

[28] Garbe, Frederik; Hancock, Robert; Hladký, Jan; Sharifzadeh, Maryam Limits of Latin Squares, Discrete analysis, Volume 2023 (2023), Paper no. 8 (Accessed 2025-01-20) | DOI | MR

[29] Garlaschelli, Diego The Weighted Random Graph Model, New Journal of Physics, Volume 11 (2009) no. 7, Paper no. 073005 (Accessed 2023-09-19) | DOI

[30] Hladký, Jan; Nachmias, Asaf; Tran, Tuan The Local Limit of the Uniform Spanning Tree on Dense Graphs, Journal of Statistical Physics, Volume 173 (2018) no. 3-4, pp. 502-545 (Accessed 2023-01-16) | DOI | MR | Zbl

[31] Hladký, Jan; Viswanathan, Gopal Random Minimum Spanning Tree and Dense Graph Limits, 2023 (Accessed 2023-10-20) | arXiv

[32] Hu, Yuanquan; Wei, Xiaoli; Yan, Junji; Zhang, Hengxi Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learning, Journal of the Franklin Institute (2023) (Accessed 2023-12-21) | DOI

[33] Humphreys, A.; Simpson, Stephen Separable Banach Space Theory Needs Strong Set Existence Axioms, Transactions of the American Mathematical Society, Volume 348 (1996) no. 10, pp. 4231-4255 | DOI | MR | Zbl

[34] Hurd, T. R.; Gleeson, J. P. On Watts’ Cascade Model with Random Link Weights, Journal of Complex Networks, Volume 1 (2013) no. 1, pp. 25-43 (Accessed 2023-09-22) | DOI | Zbl

[35] Janson, Svante Graphons, Cut Norm and Distance, Couplings and Rearrangements, New York Journal of Mathematics, Volume 4 (2013) (Accessed 2023-10-26) | arXiv

[36] Jog, Varun; Loh, Po-Ling Recovering Communities in Weighted Stochastic Block Models, 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE, Monticello, IL (2015), pp. 1308-1315 (Accessed 2023-12-21) | DOI

[37] Kallenberg, Olav Foundations of modern probability, Probability and its Applications (New York), Springer-Verlag, New York, 2002, xx+638 pages | DOI | MR

[38] Kallenberg, Olav Random Measures, Theory and Applications, Probability Theory and Stochastic Modelling, 77, Springer International Publishing, Cham, 2017 | DOI | MR

[39] Keriven, Nicolas; Vaiter, Samuel What Functions Can Graph Neural Networks Compute on Random Graphs? The Role of Positional Encoding, Advances in Neural Information Processing Systems, Volume 36, Curran Associates, Inc. (2023), pp. 11823-11849 https://proceedings.neurips.cc/paper_files/paper/2023/file/271ec4d1a9ff5e6b81a6e21d38b1ba96-Paper-Conference.pdf

[40] Kiss, István Z.; Miller, Joel C.; Simon, Péter L. Mathematics of Epidemics on Networks: From Exact to Approximate Models, Interdisciplinary Applied Mathematics, 46, Springer International Publishing, Cham, 2017 (Accessed 2023-09-29) | DOI | MR

[41] Kolossváry, István; Ráth, Balázs Multigraph Limits and Exchangeability, Acta Mathematica Hungarica, Volume 130 (2011) no. 1-2, pp. 1-34 (Accessed 2024-01-04) | DOI | MR | Zbl

[42] Kunszenti-Kovács, Dávid; Lovász, László; Szegedy, Balázs Multigraph Limits, Unbounded Kernels, and Banach Space Decorated Graphs, Journal of Functional Analysis, Volume 282 (2022) no. 2, Paper no. 109284 (Accessed 2023-10-24) | DOI | MR | Zbl

[43] Lacker, Daniel; Soret, Agathe A Label-State Formulation of Stochastic Graphon Games and Approximate Equilibria on Large Networks, Mathematics of Operations Research (2022), Paper no. moor.2022.1329 (Accessed 2023-12-21) | DOI | MR | Zbl

[44] Lelarge, Marc; Massoulie, Laurent; Xu, Jiaming Reconstruction in the Labeled Stochastic Block Model, 2013 IEEE Information Theory Workshop (ITW), IEEE, Sevilla, Spain (2013), pp. 1-5 (Accessed 2023-12-21) | DOI

[45] Lewis, Theodore Gyle; Lewis, T. G. Network Science: Theory and Practice, Wiley, Hoboken, NJ, 2009

[46] Lovász, László Large networks and graph limits, 60, American Mathematical Society, Colloquium Publications, 2012 | MR

[47] Lovász, László; Szegedy, Balázs Limits of Dense Graph Sequences, Journal of Combinatorial Theory, Series B, Volume 96 (2006) no. 6, pp. 933-957 (Accessed 2023-09-18) | DOI | MR | Zbl

[48] Lovász, László; Szegedy, Balázs Szemerédi’s Lemma for the Analyst, GAFA Geometric And Functional Analysis, Volume 17 (2007) no. 1, pp. 252-270 (Accessed 2023-02-27) | DOI | MR | Zbl

[49] Lovász, László; Szegedy, Balázs Limits of Compact Decorated Graphs, 2010 (Accessed 2023-10-24) | arXiv

[50] Newman, M. E. J. The Structure and Function of Complex Networks, SIAM Review, Volume 45 (2003) no. 2, pp. 167-256 (Accessed 2023-09-26) | DOI | MR | Zbl

[51] Purves, Robert Bimeasurable functions, Fund. Math., Volume 58 (1966), pp. 149-157 | DOI | MR | Zbl

[52] Varadarajan, Veeravalli S. Weak Convergence of Measures on Separable Metric Spaces, Sankhyā: The Indian Journal of Statistics (1933-1960), Volume 19 (1958) no. 1/2, pp. 15-22 http://www.jstor.org/stable/25048364 | MR | Zbl

[53] Xu, Jiaming; Massoulié, Laurent; Lelarge, Marc Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results, Proceedings of The 27th Conference on Learning Theory (Balcan, Maria Florina; Feldman, Vitaly; Szepesvári, Csaba, eds.) (Proceedings of Machine Learning Research), Volume 35, PMLR, Barcelona, Spain (2014), pp. 903-920 https://proceedings.mlr.press/v35/xu14.html

[54] Xu, Min; Jog, Varun; Loh, Po-Ling Optimal Rates for Community Estimation in the Weighted Stochastic Block Model, The Annals of Statistics, Volume 48 (2020) no. 1, pp. 183-204 (Accessed 2023-12-21) | DOI | MR | Zbl

[55] Yun, Se-Young; Proutiere, Alexandre Optimal Cluster Recovery in the Labeled Stochastic Block Model, Advances in Neural Information Processing Systems (Lee, D.; Sugiyama, M.; Luxburg, U.; Guyon, I.; Garnett, R., eds.), Volume 29, Curran Associates, Inc. (2016) https://proceedings.neurips.cc/paper_files/paper/2016/file/a8849b052492b5106526b2331e526138-Paper.pdf

Cited by Sources: