Thematische Bibliographien / Probability-Graphons / Zeitschriftenartikel

Um die anderen Arten von Veröffentlichungen zu diesem Thema anzuzeigen, folgen Sie diesem Link: Probability-Graphons.

Zeitschriftenartikel zum Thema „Probability-Graphons“

Autor: Grafiati

Veröffentlicht am 14. Dezember 2024

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit Top-17 Zeitschriftenartikel für die Forschung zum Thema "Probability-Graphons" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Sehen Sie die Zeitschriftenartikel für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.

Ackerman, Nate, Cameron E. Freer, Younesse Kaddar, Jacek Karwowski, Sean Moss, Daniel Roy, Sam Staton und Hongseok Yang. „Probabilistic Programming Interfaces for Random Graphs: Markov Categories, Graphons, and Nominal Sets“. Proceedings of the ACM on Programming Languages 8, POPL (05.01.2024): 1819–49. http://dx.doi.org/10.1145/3632903.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

McMillan, Audra, und Adam Smith. „When is non-trivial estimation possible for graphons and stochastic block models?‡“. Information and Inference: A Journal of the IMA 7, Nr. 2 (23.08.2017): 169–81. http://dx.doi.org/10.1093/imaiai/iax010.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

ZHAO, YUFEI. „On the Lower Tail Variational Problem for Random Graphs“. Combinatorics, Probability and Computing 26, Nr. 2 (16.08.2016): 301–20. http://dx.doi.org/10.1017/s0963548316000262.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Braides, Andrea, Paolo Cermelli und Simone Dovetta. „Γ-limit of the cut functional on dense graph sequences“. ESAIM: Control, Optimisation and Calculus of Variations 26 (2020): 26. http://dx.doi.org/10.1051/cocv/2019029.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

HATAMI, HAMED, und SERGUEI NORINE. „The Entropy of Random-Free Graphons and Properties“. Combinatorics, Probability and Computing 22, Nr. 4 (16.05.2013): 517–26. http://dx.doi.org/10.1017/s0963548313000175.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Keliger, Dániel, Illés Horváth und Bálint Takács. „Local-density dependent Markov processes on graphons with epidemiological applications“. Stochastic Processes and their Applications 148 (Juni 2022): 324–52. http://dx.doi.org/10.1016/j.spa.2022.03.001.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Backhausz, Ágnes, und Dávid Kunszenti-Kovács. „On the dense preferential attachment graph models and their graphon induced counterpart“. Journal of Applied Probability 56, Nr. 2 (Juni 2019): 590–601. http://dx.doi.org/10.1017/jpr.2019.34.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Backhausz, Ágnes, und Balázs Szegedy. „Action convergence of operators and graphs“. Canadian Journal of Mathematics, 17.09.2020, 1–50. http://dx.doi.org/10.4153/s0008414x2000070x.

Der volle Inhalt der Quelle

Annotation:

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.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Markering, Maarten. „The Large Deviation Principle for Inhomogeneous Erdős–Rényi Random Graphs“. Journal of Theoretical Probability, 14.06.2022. http://dx.doi.org/10.1007/s10959-022-01181-1.

Der volle Inhalt der Quelle

Annotation:

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).

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Janssen, Jeannette, und Aaron Smith. „Reconstruction of line-embeddings of graphons“. Electronic Journal of Statistics 16, Nr. 1 (01.01.2022). http://dx.doi.org/10.1214/21-ejs1940.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Oh, Sewoong, Soumik Pal, Raghav Somani und Raghavendra Tripathi. „Gradient Flows on Graphons: Existence, Convergence, Continuity Equations“. Journal of Theoretical Probability, 03.07.2023. http://dx.doi.org/10.1007/s10959-023-01271-8.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Abbe, Emmanuel, Shuangping Li und Allan Sly. „Learning sparse graphons and the generalized Kesten–Stigum threshold“. Annals of Statistics 51, Nr. 2 (01.04.2023). http://dx.doi.org/10.1214/23-aos2262.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Lunde, Robert, und Purnamrita Sarkar. „Subsampling Sparse Graphons Under Minimal Assumptions“. Biometrika, 02.06.2022. http://dx.doi.org/10.1093/biomet/asac032.

Der volle Inhalt der Quelle

Annotation:

Summary We study the properties of two subsampling procedures for networks, (vertex subsampling and p-subsampling), under the sparse graphon model. The consistency of network subsampling is demonstrated under the minimal assumptions of weak convergence of corresponding network statistics and an (expected) subsample size growing to infinity slower than the number of vertices in the network. Furthermore, under appropriate sparsity conditions, we derive limiting distributions for the nonzero eigenvalues of an adjacency matrix under the sparse graphon model. Our weak convergence result implies the consistency of our subsampling procedures for eigenvalues under appropriate conditions.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Chatterjee, Anirban, und Rajat Subhra Hazra. „Spectral properties for the Laplacian of a generalized Wigner matrix“. Random Matrices: Theory and Applications, 14.10.2021. http://dx.doi.org/10.1142/s2010326322500265.

Der volle Inhalt der Quelle

Annotation:

In this paper, we consider the spectrum of a Laplacian matrix, also known as Markov matrices where the entries of the matrix are independent but have a variance profile. Motivated by recent works on generalized Wigner matrices we assume that the variance profile gives rise to a sequence of graphons. Under the assumption that these graphons converge, we show that the limiting spectral distribution converges. We give an expression for the moments of the limiting measure in terms of graph homomorphisms. In some special cases, we identify the limit explicitly. We also study the spectral norm and derive the order of the maximum eigenvalue. We show that our results cover Laplacians of various random graphs including inhomogeneous Erdős–Rényi random graphs, sparse W-random graphs, stochastic block matrices and constrained random graphs.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Bhattacharya, Bhaswar B., Anirban Chatterjee und Svante Janson. „Fluctuations of subgraph counts in graphon based random graphs“. Combinatorics, Probability and Computing, 09.12.2022, 1–37. http://dx.doi.org/10.1017/s0963548322000335.

Der volle Inhalt der Quelle

Annotation:

Abstract Given a graphon $W$ and a finite simple graph $H$ , with vertex set $V(H)$ , denote by $X_n(H, W)$ the number of copies of $H$ in a $W$ -random graph on $n$ vertices. The asymptotic distribution of $X_n(H, W)$ was recently obtained by Hladký, Pelekis, and Šileikis [17] in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$ . Towards this we introduce a notion of $H$ -regularity of graphons and show that if the graphon $W$ is not $H$ -regular, then $X_n(H, W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-\frac{1}{2}}$ . On the other hand, if $W$ is $H$ -regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H, W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$ . Our proofs use the asymptotic theory of generalised $U$ -statistics developed by Janson and Nowicki [22]. We also investigate the structure of $H$ -regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$ -regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H, W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$ . We give an example of this degeneracy with $H=K_{1, 3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Bet, Gianmarco, Fabio Coppini und Francesca Romana Nardi. „Weakly interacting oscillators on dense random graphs“. Journal of Applied Probability, 30.06.2023, 1–24. http://dx.doi.org/10.1017/jpr.2023.34.

Der volle Inhalt der Quelle

Annotation:

Abstract We consider a class of weakly interacting particle systems of mean-field type. The interactions between the particles are encoded in a graph sequence, i.e. two particles are interacting if and only if they are connected in the underlying graph. We establish a law of large numbers for the empirical measure of the system that holds whenever the graph sequence is convergent to a graphon. The limit is the solution of a non-linear Fokker–Planck equation weighted by the (possibly random) graphon limit. In contrast with the existing literature, our analysis focuses on both deterministic and random graphons: no regularity assumptions are made on the graph limit and we are able to include general graph sequences such as exchangeable random graphs. Finally, we identify the sequences of graphs, both random and deterministic, for which the associated empirical measure converges to the classical McKean–Vlasov mean-field limit.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Blekherman, Grigoriy, Annie Raymond und Fan Wei. „Undecidability of polynomial inequalities in weighted graph homomorphism densities“. Forum of Mathematics, Sigma 12 (2024). http://dx.doi.org/10.1017/fms.2024.19.

Der volle Inhalt der Quelle

Annotation:

Abstract Many problems and conjectures in extremal combinatorics concern polynomial inequalities between homomorphism densities of graphs where we allow edges to have real weights. Using the theory of graph limits, we can equivalently evaluate polynomial expressions in homomorphism densities on kernels W, that is, symmetric, bounded and measurable functions W from $[0,1]^2 \to \mathbb {R}$ . In 2011, Hatami and Norin proved a fundamental result that it is undecidable to determine the validity of polynomial inequalities in homomorphism densities for graphons (i.e., the case where the range of W is $[0,1]$ , which corresponds to unweighted graphs or, equivalently, to graphs with edge weights between $0$ and $1$ ). The corresponding problem for more general sets of kernels, for example, for all kernels or for kernels with range $[-1,1]$ , remains open. For any $a> 0$ , we show undecidability of polynomial inequalities for any set of kernels which contains all kernels with range $\{0,a\}$ . This result also answers a question raised by Lovász about finding computationally effective certificates for the validity of homomorphism density inequalities in kernels.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!