First Passage Percolation on Inhomogeneous Random Graphs

Kolossváry, István and Komjáthy, Júlia (2015) First Passage Percolation on Inhomogeneous Random Graphs. ADVANCES IN APPLIED PROBABILITY, 47 (2). pp. 589-610. ISSN 0001-8678

Preview

Text 1201.3137.pdf Available under License Creative Commons Attribution. Download (591kB) | Preview

Abstract

We investigate first passage percolation on inhomogeneous ran- dom graphs. The random graph model G(n, κ) we study is the model introduced by Bollob´as, Janson and Riordan in, where each vertex has a type from a type space S and edge probabilities are indepen- dent, but depending on the types of the end vertices. Each edge is given an independent exponential weight. We determine the distri- bution of the weight of the shortest path between uniformly chosen vertices in the giant component and show that the hopcount, i.e. the number of edges on this minimal weight path, properly normalized follows a central limit theorem. We handle the cases where ˜λn → ˜λ is finite or infinite, under the assumption that the average number of neighbors ˜λn of a vertex is independent of the type. The paper is a generalization of written by Bhamidi, van der Hofstad and Hooghiemstra, where FPP is explored on the Erd˝os-R´enyi graphs.

Actions (login required)

Edit Item