Probability-graphons: Limits of large dense weighted graphs

Abstract

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.

References in corpus (22)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Structural Vulnerability of the North American Power Grid
• The weighted random graph model
• First passage percolation on random graphs with finite mean degrees
• Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
• Graphons, cut norm and distance, couplings and rearrangements
• The diameter of weighted random graphs
• Limits of compact decorated graphs
• The cut metric, random graphs, and branching processes
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Multicolour containers and the entropy of decorated graph limits
• The local limit of the uniform spanning tree on dense graphs
• Opinion Dynamics on Graphon: the piecewise constant case
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
• Graph Limit for Interacting Particle Systems on Weighted Random Graphs
• A label-state formulation of stochastic graphon games and approximate equilibria on large networks
• Random minimum spanning tree and dense graph limits
• Weighted random--geometric and random--rectangular graphs: Spectral and eigenfunction properties of the adjacency matrix
• Path convergence of Markov chains on large graphs
• Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learning