Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVoter models on subcritical inhomogeneous random graphs
153
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The voter model is a classical interacting particle system modelling how consensus is formed across a network. We analyse the time to consensus for the voter model when the underlying graph is a subcritical scale-free random graph. Moreover, we generalise the model to include a `temperature parameter. The interplay between the temperature and the structure of the random graph leads to a very rich phase diagram, where in the different phases different parts of the underlying geometry dominate the time to consensus. Finally, we also consider a discursive voter model, where voters discuss their opinions with their neighbours. Our proofs rely on the well-known duality to coalescing random walks and a detailed understanding of the structure of the random graphs.
rate research
Read More
A bootstrap percolation process on a graph G is an infection process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round every uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r > 1 is fixed. We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank 1. Assuming that initially every vertex is infected independently with probability p > 0, we provide a law of large numbers for the number of vertices that will have been infected by the end of the process. We also focus on a special case of such random graphs which exhibit a power-law degree distribution with exponent in (2,3). The first two authors have shown the existence of a critical function a_c(n) such that a_c(n)=o(n) with the following property. Let n be the number of vertices of the underlying random graph and let a(n) be the number of the vertices that are initially infected. Assume that a set of a(n) vertices is chosen randomly and becomes externally infected. If a(n) << a_c(n), then the process does not evolve at all, with high probability as n grows, whereas if a(n)>> a_c(n), then with high probability the final set of infected vertices is linear. Using the techniques of the previous theorem, we give the precise asymptotic fraction of vertices which will be eventually infected when a(n) >> a_c (n) but a(n) = o(n). Note that this corresponds to the case where p approaches 0.
Consider a collection of random variables attached to the vertices of a graph. The reconstruction problem requires to estimate one of them given `far away observations. Several theoretical results (and simple algorithms) are available when their joint probability distribution is Markov with respect to a tree. In this paper we consider the case of sequences of random graphs that converge locally to trees. In particular, we develop a sufficient condition for the tree and graph reconstruction problem to coincide. We apply such condition to colorings of random graphs. Further, we characterize the behavior of Ising models on such graphs, both with attractive and random interactions (respectively, `ferromagnetic and `spin glass).
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.
Motivated by limits of critical inhomogeneous random graphs, we construct a family of sequences of measured metric spaces that we call continuous multiplicative graphs, that are expected to be the universal limit of graphs related to the multiplicative coalescent (the ErdH{o}s--Renyi random graph, more generally the so-called rank-one inhomogeneous random graphs of various types, and the configuration model). At the discrete level, the construction relies on a new point of view on (discrete) inhomogeneous random graphs that involves an embedding into a Galton--Watson forest. The new representation allows us to demonstrate that a processus that was already present in the pionnering work of Aldous [Ann. Probab., vol.~25, pp.~812--854, 1997] and Aldous and Limic [Electron. J. Probab., vol.~3, pp.~1--59, 1998] about the multiplicative coalescent actually also (essentially) encodes the limiting metric: The discrete embedding of random graphs into a Galton--Watson forest is paralleled by an embedding of the encoding process into a Levy process which is crucial in proving the very existence of the local time functionals on which the metric is based; it also yields a transparent approach to compactness and fractal dimensions of the continuous objects. In a companion paper, we show that the continuous Levy graphs are indeed the scaling limit of inhomogeneous random graphs.
We study the typical behavior of a generalized version of Googles PageRank algorithm on a large family of inhomogeneous random digraphs. This family includes as special cases direct
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
