Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe giant in random graphs is almost local
66
0
0.0
(
0
)
Authors
Remco van der Hofstad
Ask ChatGPT about the research
No Arabic abstract
Local convergence techniques have become a key methodology to study random graphs in sparse settings where the average degree remains bounded. However, many random graph properties do not directly converge when the random graph converges locally. A notable, and important, random graph property that does not follow from local convergence is the size and uniqueness of the giant component. We provide a simple criterion that guarantees that local convergence of a random graph implies the convergence of the proportion of vertices in the maximal connected component. We further show that, when this condition holds, the local properties of the giant are also described by the local limit. We apply this novel method to the configuration model as a proof of concept, reproving a result that is well-established. As a side result this proof, we show that the proof also implies the small-world nature of the configuration model.
rate research
Read More
Consider a set of $n$ vertices, where each vertex has a location in $mathbb{R}^d$ that is sampled uniformly from the unit cube in $mathbb{R}^d$, and a weight associated to it. Construct a random graph by placing edges independently for each vertex pair with a probability that is a function of the distance between the locations, and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $mathbb{R}^d$ with vertex locations given by a homogeneous Poisson point process, having weights which are i.i.d. copies of limiting vertex weights. Our setup covers many sparse geometric random graph models from the literature, including Geometric Inhomogeneous Random Graphs (GIRGs), Hyperbolic Random Graphs, Continuum Scale-Free Percolation and Weight-dependent Random Connection Models. We prove that the limiting degree distribution is mixed Poisson, and the typical degree sequence is uniformly integrable, and obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a by-product of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting.
The aim of this paper is the study of the strong local survival property for discrete-time and continuous-time branching random walks. We study this property by means of an infinite dimensional generating function G and a maximum principle which, we prove, is satisfied by every fixed point of G. We give results about the existence of a strong local survival regime and we prove that, unlike local and global survival, in continuous time, strong local survival is not a monotone property in the general case (though it is monotone if the branching random walk is quasi transitive). We provide an example of an irreducible branching random walk where the strong local property depends on the starting site of the process. By means of other counterexamples we show that the existence of a pure global phase is not equivalent to nonamenability of the process, and that even an irreducible branching random walk with the same branching law at each site may exhibit non-strong local survival. Finally we show that the generating function of a irreducible BRW can have more than two fixed points; this disproves a previously known result.
We study a generalisation of the random recursive tree (RRT) model and its multigraph counterpart, the uniform directed acyclic graph (DAG). Here, vertices are equipped with a random vertex-weight representing initial inhomogeneities in the network, so that a new vertex connects to one of the old vertices with a probability that is proportional to their vertex-weight. We first identify the asymptotic degree distribution of a uniformly chosen vertex for a general vertex-weight distribution. For the maximal degree, we distinguish several classes that lead to different behaviour: For bounded vertex-weights we obtain results for the maximal degree that are similar to those observed for RRTs and DAGs. If the vertex-weights have unbounded support, then the maximal degree has to satisfy the right balance between having a high vertex-weight and being born early. For vertex-weights in the Frechet maximum domain of attraction the first order behaviour of the maximal degree is random, while for those in the Gumbel maximum domain of attraction the leading order is deterministic. Surprisingly, in the latter case, the second order is random when considering vertices in a compact window in the optimal region, while it becomes deterministic when considering all vertices.
We study the critical behavior for percolation on inhomogeneous random networks on $n$ vertices, where the weights of the vertices follow a power-law distribution with exponent $tau in (2,3)$. Such networks, often referred to as scale-free networks, exhibit critical behavior when the percolation probability tends to zero at an appropriate rate, as $ntoinfty$. We identify the critical window for a host of scale-free random graph models such as the Norros-Reittu model, Chung-Lu model and generalized random graphs. Surprisingly, there exists a finite time inside the critical window, after which, we see a sudden emergence of a tiny giant component. This is a novel behavior which is in contrast with the critical behavior in other known universality classes with $tau in (3,4)$ and $tau >4$. Precisely, for edge-retention probabilities $pi_n = lambda n^{-(3-tau)/2}$, there is an explicitly computable $lambda_c>0$ such that the critical window is of the form $lambda in (0,lambda_c),$ where the largest clusters have size of order $n^{beta}$ with $beta=(tau^2-4tau+5)/[2(tau-1)]in[sqrt{2}-1, tfrac{1}{2})$ and have non-degenerate scaling limits, while in the supercritical regime $lambda > lambda_c$, a unique `tiny giant component of size $sqrt{n}$ emerges. For $lambda in (0,lambda_c),$ the scaling limit of the maximum component sizes can be described in terms of components of a one-dimensional inhomogeneous percolation model on $mathbb{Z}_+$ studied in a seminal work by Durrett and Kesten. For $lambda>lambda_c$, we prove that the sudden emergence of the tiny giant is caused by a phase transition inside a smaller core of vertices of weight $Omega(sqrt{n})$.
Inspired by a concept in comparative genomics, we investigate properties of randomly chosen members of G_1(m,n,t), the set of bipartite graphs with $m$ left vertices, n right vertices, t edges, and each vertex of degree at least one. We give asymptotic results for the number of such graphs and the number of $(i,j)$ trees they contain. We compute the thresholds for the emergence of a giant component and for the graph to be connected.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
