Probability-graphons: Limits of large dense weighted graphs

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi mathvariant="normal">m</mml:mi> </mml:msub> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi mathvariant="normal">m</mml:mi> </mml:msub> </mml:math> , 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi mathvariant="normal">m</mml:mi> </mml:msub> </mml:math> . Eventually, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs.