An official website of the United States government
This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $$5 5$, any $L^p$-graphon $$w$$ can be approximated by a Robinson graphon, with error of the approximation bounded in terms of $$\Lambda(w)$$. When viewing $$w$$ as a noisy version of a Robinson graphon, our method provides a concrete recipe for recovering a cut-norm approximation of a noiseless $$w$$. Given that any symmetric matrix is a special type of graphon, our results can be applicable to symmetric matrices of any size. Our work extends and improves previous results, where a similar question for the special case of $$L^\infty$$-graphons was answered.
more »
« less
Fluctuations of subgraph counts in graphon based random graphs
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.
more »
« less
- Award ID(s):
- 2046393
- PAR ID:
- 10425511
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 32
- Issue:
- 3
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 428 to 464
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Scaling limits and universality: Critical percolation on weighted graphs converging to an 𝐿³ graphonWe develop a general universality technique for establishing metric scaling limits of critical random discrete structures exhibiting mean-field behavior that requires four ingredients: (i) from the barely subcritical regime to the critical window, components merge approximately like the multiplicative coalescent, (ii) asymptotics of the susceptibility functions are the same as that of the Erdős-Rényi random graph, (iii) asymptotic negligibility of the maximal component size and the diameter in the barely subcritical regime, and (iv) macroscopic averaging of distances between vertices in the barely subcritical regime. As an application of the general universality theorem, we establish, under some regularity conditions, the critical percolation scaling limit of graphs that converge, in a suitable topology, to an graphon. In particular, we define a notion of the critical window in this setting. The assumption ensures that the model is in the Erdős-Rényi universality class and that the scaling limit is Brownian. Our results do not assume any specific functional form for the graphon. As a consequence of our results on graphons, we obtain the metric scaling limit for Aldous-Pittel’s RGIV model inside the critical window (see D.J. Aldous and B. Pittel [Random Structures Algorithms 17 (2000), pp. 79–102]). Our universality principle has applications in a number of other problems including in the study of noise sensitivity of critical random graphs (see E. Lubetzky and Y. Peled [Israel J. Math. 252 (2022), pp. 187–214]). In Bhamidi et al. [Scaling limits and universality II: geometry of maximal components in dynamic random graph models in the critical regime, In preparation], we use our universality theorem to establish the metric scaling limit of critical bounded size rules. Our method should yield the critical metric scaling limit of Ruciński and Wormald’s random graph process with degree restrictions provided an additional technical condition about the barely subcritical behavior of this model can be proved (see A. Ruciński and N. C. Wormald [Combin. Probab. Comput. 1 (1992), pp. 169–180]).more » « less
-
We investigate the H-property for step-graphons. Specifically, we sample graphs G_n on n nodes from a step-graphon and evaluate the probability that G_n has a Hamiltonian decomposition in the asymptotic regime as n goes to infinity. It has been shown in our earlier work that for almost all step-graphons, this probability converges to either zero or one. We focus in this paper on the residual case where the zero-one law does not apply. We show that the limit of the probability still exists and provide an explicit expression of it. We present a complete proof of the result and validate it through numerical studies.more » « less
-
Abstract Graph signal processing (GSP) extends classical signal processing to signals defined on graphs, enabling filtering, spectral analysis, and sampling of data generated by networks of various kinds. Graphon signal processing (GnSP) develops this framework further by employing the theory of graphons. Graphons are measurable functions on the unit square that represent graphs and limits of convergent graph sequences. The use of graphons provides stability of GSP methods to stochastic variability in network data and improves computational efficiency for very large networks. We use GnSP to address the stimulus identification problem (SIP) in computational and biological neural networks. The SIP is an inverse problem that aims to infer the unknown stimulus sfrom the observed network output f. We first validate the approach in spiking neural network simulations and then analyze calcium imaging recordings. Graphon-based spectral projections yield trial-invariant, low-dimensional embeddings that improve stimulus classification over principal component analysis and discrete GSP baselines. The embeddings remain stable under variations in network stochasticity, providing robustness to different network sizes and noise levels. To the best of our knowledge, this is the first application of GnSP to biological neural networks, opening new avenues for graphon-based analysis in neuroscience.more » « less
-
Call a hereditary family F of graphs strongly persistent if there exists a graphon W such that in all subgraphons W0 of W , F is precisely the class of finite graphs that have positive density in W0. Our first result is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. We call graphons with the self-similarity property above weakly random. A hereditary family F is said to have the weakly random Erdos–Hajnal property (WR) if every graphon that is a limit of graphs in F has a weakly random subgraphon. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with “few” prime graphs. We also extend some of the results above to structures in finite relational languages by using the theory of theons.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1017/S0963548322000335
