Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTopological properties of P.A. random graphs with edge-step functions
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this work we investigate a preferential attachment model whose parameter is a function $f:mathbb{N}to[0,1]$ that drives the asymptotic proportion between the numbers of vertices and edges of the graph. We investigate topological features of the graphs, proving general bounds for the diameter and the clique number. Our results regarding the diameter are sharp when $f$ is a regularly varying function at infinity with strictly negative index of regular variation $-gamma$. For this particular class, we prove a characterization for the diameter that depends only on $-gamma$. More specifically, we prove that the diameter of such graphs is of order $1/gamma$ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of slowly varying functions are also obtained. The almost sure convergence for the properly normalized logarithm of the clique number of the graphs generated by slowly varying functions is also proved.
rate research
Read More
We propose a random graph model with preferential attachment rule and emph{edge-step functions} that govern the growth rate of the vertex set. We study the effect of these functions on the empirical degree distribution of these random graphs. More specifically, we prove that when the edge-step function $f$ is a emph{monotone regularly varying function} at infinity, the sequence of graphs associated to it obeys a power-law degree distribution whose exponent is related to the index of regular variation of $f$ at infinity whenever said index is greater than $-1$. When the regularly variation index is less than or equal to $-1$, we show that the proportion of vertices with degree smaller than any given constant goes to $0$ a. s..
Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $dgeq3$. We prove that, with probability $1-N^{-1+{varepsilon}}$ for any ${varepsilon} >0$, the following two properties hold as $N to infty$ provided that $dgeq3$: (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten-McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound in $N$, i.e. $lambda_2, |lambda_N|leq 2+N^{-c}$. (ii) All eigenvectors of random $d$-regular graphs are completely delocalized.
For random $d$-regular graphs on $N$ vertices with $1 ll d ll N^{2/3}$, we develop a $d^{-1/2}$ expansion of the local eigenvalue distribution about the Kesten-McKay law up to order $d^{-3}$. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of ErdH{o}s-Renyi graphs of the same average degree. As a first application, for $1 ll d ll N^{2/3}$, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by $(2 + o(1)) sqrt{d - 1}$. As a second application, for $N^{2/9} ll d ll N^{1/3}$, we prove that the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of $d$, $52%$ of all $d$-regular graphs have second-largest eigenvalue strictly less than $2 sqrt{d - 1}$.
In this work we perform a detailed statistical analysis of topological and spectral properties of random geometric graphs (RGGs); a graph model used to study the structure and dynamics of complex systems embedded in a two dimensional space. RGGs, $G(n,ell)$, consist of $n$ vertices uniformly and independently distributed on the unit square, where two vertices are connected by an edge if their Euclidian distance is less or equal than the connection radius $ell in [0,sqrt{2}]$. To evaluate the topological properties of RGGs we chose two well-known topological indices, the Randic index $R(G)$ and the harmonic index $H(G)$. While we characterize the spectral and eigenvector properties of the corresponding randomly-weighted adjacency matrices by the use of random matrix theory measures: the ratio between consecutive eigenvalue spacings, the inverse participation ratios and the information or Shannon entropies $S(G)$. First, we review the scaling properties of the averaged measures, topological and spectral, on RGGs. Then we show that: (i) the averaged--scaled indices, $leftlangle R(G) rightrangle$ and $leftlangle H(G) rightrangle$, are highly correlated with the average number of non-isolated vertices $leftlangle V_times(G) rightrangle$; and (ii) surprisingly, the averaged--scaled Shannon entropy $leftlangle S(G) rightrangle$ is also highly correlated with $leftlangle V_times(G) rightrangle$. Therefore, we suggest that very reliable predictions of eigenvector properties of RGGs could be made by computing topological indices.
We consider the Erdos-Renyi random graph G(n,p) inside the critical window, where p = 1/n + lambda * n^{-4/3} for some lambda in R. We proved in a previous paper (arXiv:0903.4730) that considering the connected components of G(n,p) as a sequence of metric spaces with the graph distance rescaled by n^{-1/3} and letting n go to infinity yields a non-trivial sequence of limit metric spaces C = (C_1, C_2, ...). These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on R_+. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Luczak, Pittel and Wierman by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
