Limits of Weighted Graphs via Random Quotients
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915877902876672 |
|---|---|
| author | Levin, Eitan Chandrasekaran, Venkat |
| author_facet | Levin, Eitan Chandrasekaran, Venkat |
| contents | We present a new notion of limits of weighted directed graphs of growing size based on convergence of their random quotients. These limits are specified in terms of random exchangeable measures on the unit square. We call our limits grapheurs and show that these are dual to graphons in a precise sense. Grapheurs are well-suited to modeling global structure in large graphs such as hubs and connections between them; previous notions of graph limits based on subgraph densities fail to adequately model such global structure as subgraphs are inherently local. Using our framework, we characterize properties of large graphs that are continuous with respect to our limits and present an edge-based sampling approach for testing them. This method relies on an edge-based analog of the Szemerédi regularity lemma, whereby we show that sampling a constant number of edges from an arbitrarily-large graph approximately preserves its quotients. Finally, we observe that the random quotients of a graph are related to each other by equipartitions, and we conclude with a characterization of such random graph models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23149 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Limits of Weighted Graphs via Random Quotients Levin, Eitan Chandrasekaran, Venkat Combinatorics Probability 05C82, 05C80, 60G57 We present a new notion of limits of weighted directed graphs of growing size based on convergence of their random quotients. These limits are specified in terms of random exchangeable measures on the unit square. We call our limits grapheurs and show that these are dual to graphons in a precise sense. Grapheurs are well-suited to modeling global structure in large graphs such as hubs and connections between them; previous notions of graph limits based on subgraph densities fail to adequately model such global structure as subgraphs are inherently local. Using our framework, we characterize properties of large graphs that are continuous with respect to our limits and present an edge-based sampling approach for testing them. This method relies on an edge-based analog of the Szemerédi regularity lemma, whereby we show that sampling a constant number of edges from an arbitrarily-large graph approximately preserves its quotients. Finally, we observe that the random quotients of a graph are related to each other by equipartitions, and we conclude with a characterization of such random graph models. |
| title | Limits of Weighted Graphs via Random Quotients |
| topic | Combinatorics Probability 05C82, 05C80, 60G57 |
| url | https://arxiv.org/abs/2512.23149 |