Probability-graphons: Limits of large dense weighted graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909645346439168 |
|---|---|
| author | Abraham, Romain Delmas, Jean-François Weibel, Julien |
| author_facet | Abraham, Romain Delmas, Jean-François Weibel, Julien |
| contents | 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_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_m$, which are satisfied for some well-know distances like the Prohorov distance, and the Fortet-Mourier and Kantorovitch-Rubinstein norms, the topology induced by the cut distance on the spaceof probability-graphons is independent from the choice of $d_m$. Eventually, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15935 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Probability-graphons: Limits of large dense weighted graphs Abraham, Romain Delmas, Jean-François Weibel, Julien Discrete Mathematics Probability 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_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_m$, which are satisfied for some well-know distances like the Prohorov distance, and the Fortet-Mourier and Kantorovitch-Rubinstein norms, the topology induced by the cut distance on the spaceof probability-graphons is independent from the choice of $d_m$. Eventually, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs. |
| title | Probability-graphons: Limits of large dense weighted graphs |
| topic | Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2312.15935 |