First Passage Percolation on Inhomogeneous Random Graphs

Details First Passage Percolation on Inhomogeneous Random Graphs First Passage Percolation on Inhomogeneous Random Graphs

2012-01-15

arxiv.org/abs/1201.3137v1

Mathematics

Probability

arXiv admin note: text overlap with arXiv:1005.4104 by other authors

Scientific paper

This paper investigates first passage percolation (FPP) on inhomogeneous random graphs (IHRG). The random graph model $G(n,\kappa)$ we first study is the so-called finite type case of the general model introduced by Bollob\'as, Janson and Riordan. Each edge of $G(n,\kappa)$ is given an independent exponential edge weight with rate 1. Our main assumption is that the average number of neighbors $\wla_n+1$ of each vertex is independent of its type. We consider the cases where $\wla_n\to\wla$ is finite or infinite. Afterwards the general model is also considered. The paper can be considered a generalization of the work of Bhamidi, van der Hofstad and Hooghimstra, where FPP is explored on the Erd\H{o}s-R\'enyi random graphs, a special case where all the vertices are of the same type. We find analogous results for the minimal weight of the path between uniformly chosen vertices in the giant component and for the hopcount, i.e. the number of edges on this minimal weight path. The proofs make use of a direct relation between FPP on the IHRG and thinned continuous-time multi-type branching processes.

Affiliated with

Also associated with

No associations

Rating

First Passage Percolation on Inhomogeneous Random Graphs 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 Inhomogeneous Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First Passage Percolation on Inhomogeneous Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409390