Auswahl der wissenschaftlichen Literatur zum Thema „Probability-Graphons“

We study semantic models of probabilistic programming languages over graphs, and establish a connection to graphons from graph theory and combinatorics. We show that every well-behaved equational theory for our graph probabilistic programming language corresponds to a graphon, and conversely, every graphon arises in this way. We provide three constructions for showing that every graphon arises from an equational theory. The first is an abstract construction, using Markov categories and monoidal indeterminates. The second and third are more concrete. The second is in terms of traditional measure theoretic probability, which covers 'black-and-white' graphons. The third is in terms of probability monads on the nominal sets of Gabbay and Pitts. Specifically, we use a variation of nominal sets induced by the theory of graphs, which covers Erdős-Rényi graphons. In this way, we build new models of graph probabilistic programming from graphons.

Abstract Block graphons (also called stochastic block models) are an important and widely studied class of models for random networks. We provide a lower bound on the accuracy of estimators for block graphons with a large number of blocks. We show that, given only the number $k$ of blocks and an upper bound $\rho$ on the values (connection probabilities) of the graphon, every estimator incurs error ${\it{\Omega}}\left(\min\left(\rho, \sqrt{\frac{\rho k^2}{n^2}}\right)\right)$ in the $\delta_2$ metric with constant probability for at least some graphons. In particular, our bound rules out any non-trivial estimation (that is, with $\delta_2$ error substantially less than $\rho$) when $k\geq n\sqrt{\rho}$. Combined with previous upper and lower bounds, our results characterize, up to logarithmic terms, the accuracy of graphon estimation in the $\delta_2$ metric. A similar lower bound to ours was obtained independently by Klopp et al.

We study the lower tail large deviation problem for subgraph counts in a random graph. Let XH denote the number of copies of H in an Erdős–Rényi random graph $\mathcal{G}(n,p)$. We are interested in estimating the lower tail probability $\mathbb{P}(X_H \le (1-\delta) \mathbb{E} X_H)$ for fixed 0 < δ < 1.Thanks to the results of Chatterjee, Dembo and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for p ≥ n−αH (and conjecturally for a larger range of p). We study this variational problem and provide a partial characterization of the so-called ‘replica symmetric’ phase. Informally, our main result says that for every H, and 0 < δ < δH for some δH > 0, as p → 0 slowly, the main contribution to the lower tail probability comes from Erdős–Rényi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite H and δ close to 1.

A sequence of graphs with diverging number of nodes is a dense graph sequence if the number of edges grows approximately as for complete graphs. To each such sequence a function, called graphon, can be associated, which contains information about the asymptotic behavior of the sequence. Here we show that the problem of subdividing a large graph in communities with a minimal amount of cuts can be approached in terms of graphons and the Γ-limit of the cut functional, and discuss the resulting variational principles on some examples. Since the limit cut functional is naturally defined on Young measures, in many instances the partition problem can be expressed in terms of the probability that a node belongs to one of the communities. Our approach can be used to obtain insights into the bisection problem for large graphs, which is known to be NP-complete.

Every graphon defines a random graph on any given number n of vertices. It was known that the graphon is random-free if and only if the entropy of this random graph is subquadratic. We prove that for random-free graphons, this entropy can grow as fast as any subquadratic function. However, if the graphon belongs to the closure of a random-free hereditary graph property, then the entropy is O(n log n). We also give a simple construction of a non-step-function random-free graphon for which this entropy is linear, refuting a conjecture of Janson.

AbstractLetting ℳ denote the space of finite measures on ℕ, and μλ ∊ ℳ denote the Poisson distribution with parameter λ, the function W : [0, 1]2 → ℳ given by W(x, y) = μc log x log y is called the PAG graphon with density c. It is known that this is the limit, in the multigraph homomorphism sense, of the dense preferential attachment graph (PAG) model with edge density c. This graphon can then in turn be used to generate the so-called W-random graphs in a natural way, and similar constructions also work in the slightly more general context of the so-called PAGκ models. The aim of this paper is to compare these dense PAGκ models with the W-random graph models obtained from the corresponding graphons. Motivated by the multigraph limit theory, we investigate the expected jumble-norm distance of the two models in terms of the number of vertices n. We present a coupling for which the expectation can be bounded from above by O(log3/2n · n−1/2), and provide a universal lower bound that is coupling-independent, but without the logarithmic term.

Abstract We present a new approach to graph limit theory that unifies and generalizes the two most well-developed directions, namely dense graph limits (even the more general $L^p$ limits) and Benjamini–Schramm limits (even in the stronger local-global setting). We illustrate by examples that this new framework provides a rich limit theory with natural limit objects for graphs of intermediate density. Moreover, it provides a limit theory for bounded operators (called P-operators) of the form $L^\infty (\Omega )\to L^1(\Omega )$ for probability spaces $\Omega $ . We introduce a metric to compare P-operators (for example, finite matrices) even if they act on different spaces. We prove a compactness result, which implies that, in appropriate norms, limits of uniformly bounded P-operators can again be represented by P-operators. We show that limits of operators, representing graphs, are self-adjoint, positivity-preserving P-operators called graphops. Graphons, $L^p$ graphons, and graphings (known from graph limit theory) are special examples of graphops. We describe a new point of view on random matrix theory using our operator limit framework.

AbstractConsider the inhomogeneous Erdős-Rényi random graph (ERRG) on n vertices for which each pair $$i,j\in \{1,\ldots ,n\}$$ i , j ∈ { 1 , … , n } , $$i\ne j,$$ i ≠ j , is connected independently by an edge with probability $$r_n(\frac{i-1}{n},\frac{j-1}{n})$$ r n ( i - 1 n , j - 1 n ) , where $$(r_n)_{n\in \mathbb {N}}$$ ( r n ) n ∈ N is a sequence of graphons converging to a reference graphonr. As a generalisation of the celebrated large deviation principle (LDP) for ERRGs by Chatterjee and Varadhan (Eur J Comb 32:1000–1017, 2011), Dhara and Sen (Large deviation for uniform graphs with given degrees, 2020. arXiv:1904.07666) proved an LDP for a sequence of such graphs under the assumption that r is bounded away from 0 and 1, and with a rate function in the form of a lower semi-continuous envelope. We further extend the results by Dhara and Sen. We relax the conditions on the reference graphon to $$(\log r, \log (1- r))\in L^1([0,1]^2)$$ ( log r , log ( 1 - r ) ) ∈ L 1 ( [ 0 , 1 ] 2 ) . We also show that, under this condition, their rate function equals a different, more tractable rate function. We then apply these results to the large deviation principle for the largest eigenvalue of inhomogeneous ERRGs and weaken the conditions for part of the analysis of the rate function by Chakrabarty et al. (Large deviation principle for the maximal eigenvalue of inhomogeneous Erdoös-Rényi random graphs, 2020. arXiv:2008.08367).

Les graphes sont des objets mathématiques qui servent à modéliser tout type de réseaux, comme les réseaux électriques, les réseaux de communications et les réseaux sociaux. Formellement un graphe est composé d'un ensemble de sommets et d'un ensemble d'arêtes reliant des paires de sommets. Les sommets représentent par exemple des individus, tandis que les arêtes représentent les interactions entre ces individus. Dans le cas d'un graphe pondéré, chaque arête possède un poids ou une décoration pouvant modéliser une distance, une intensité d'interaction, une résistance. La modélisation de réseaux réels fait souvent intervenir de grands graphes qui ont un grand nombre de sommets et d'arêtes.La première partie de cette thèse est consacrée à l'introduction et à l'étude des propriétés des objets limites des grands graphes pondérés : les graphons de probabilités. Ces objets sont une généralisation des graphons introduits et étudiés par Lovász et ses co-auteurs dans le cas des graphes sans poids sur les arêtes. À partir d'une distance induisant la topologie faible sur les mesures, nous définissons une distance de coupe sur les graphons de probabilités. Nous exhibons un critère de tension pour les graphons de probabilités lié à la compacité relative dans la distance de coupe. Enfin, nous prouvons que cette topologie coïncide avec la topologie induite par la convergence en distribution des sous-graphes échantillonnés. Dans la deuxième partie de cette thèse, nous nous intéressons aux modèles markoviens cachés indexés par des arbres. Nous montrons la consistance forte et la normalité asymptotique de l'estimateur de maximum de vraisemblance pour ces modèles sous des hypothèses standards. Nous montrons un théorème ergodique pour des chaînes de Markov branchantes indexés par des arbres avec des formes générales. Enfin, nous montrons que pour une chaîne stationnaire et réversible, le graphe ligne est la forme d'arbre induisant une variance minimale pour l'estimateur de moyenne empirique parmi les arbres avec un nombre donné de sommets
Graphs are mathematical objects used to model all kinds of networks, such as electrical networks, communication networks, and social networks. Formally, a graph consists of a set of vertices and a set of edges connecting pairs of vertices. The vertices represent, for example, individuals, while the edges represent the interactions between these individuals. In the case of a weighted graph, each edge has a weight or a decoration that can model a distance, an interaction intensity, or a resistance. Modeling real-world networks often involves large graphs with a large number of vertices and edges.The first part of this thesis is dedicated to introducing and studying the properties of the limit objects of large weighted graphs : probability-graphons. These objects are a generalization of graphons introduced and studied by Lovász and his co-authors in the case of unweighted graphs. Starting from a distance that induces the weak topology on measures, we define a cut distance on probability-graphons. We exhibit a tightness criterion for probability-graphons related to relative compactness in the cut distance. Finally, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs. In the second part of this thesis, we focus on hidden Markov models indexed by trees. We show the strong consistency and asymptotic normality of the maximum likelihood estimator for these models under standard assumptions. We prove an ergodic theorem for branching Markov chains indexed by trees with general shapes. Finally, we show that for a stationary and reversible chain, the line graph is the tree shape that induces the minimal variance for the empirical mean estimator among trees with a given number of vertices