First passage percolation on the Erdős-Rényi random graph

Details First passage percolation on the Erdős-Rényi random graph First passage percolation on the Erdős-Rényi random graph

2010-05-22

arxiv.org/abs/1005.4104v1

Mathematics

Probability

Scientific paper

In this paper we explore first passage percolation (FPP) on the Erd\H{o}s-R\'enyi random graph $G_n(p_n)$, where each edge is given an independent exponential edge weight with rate 1. In the sparse regime, i.e., when $np_n\to \lambda>1,$ we find refined asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (i.e., the number of edges) on this minimal weight path. More precisely, we prove a central limit theorem for the hopcount, with asymptotic mean and variance both equal to $\lambda/(\lambda-1)\log{n}$. Furthermore, we prove that the minimal weight centered by $\log{n}/(\lambda-1)$ converges in distribution. We also investigate the dense regime, where $np_n \to \infty$. We find that although the base graph is a {\it ultra small} (meaning that graph distances between uniformly chosen vertices are $o(\log{n})$), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount $H_n$ satisfies the universality property that whatever be the value of $p_n$, \ $H_n/\log{n}\to 1$ in probability and, more precisely, $(H_n-\beta_n\log{n})/\sqrt{\log{n}}$, where $\beta_n=\lambda_n/(\lambda_n-1)$, has a limiting standard normal distribution. The constant $\beta_n$ can be replaced by 1 precisely when $\lambda_n\gg \sqrt{\log{n}}$, a case that has appeared in the literature (under stronger conditions on $\lambda_n$). We also find bounds for the maximal weight and maximal hopcount between vertices in the graph. This paper continues the investigation of FPP initiated by the authors. Compared to the setting on the configuration model studied in \cite{BHHS08}, the proofs presented here are much simpler due to a direct relation between FPP on the Erd\H{o}s-R\'enyi random graph and thinned continuous-time branching processes.

Affiliated with

Also associated with

No associations

Rating

First passage percolation on the Erdős-Rényi random graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with First passage percolation on the Erdős-Rényi random graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First passage percolation on the Erdős-Rényi random graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412711