First passage percolation on inhomogeneous random graphs

I. Kolossváry, J. Komjathy

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

6 Citaten (Scopus)


In this paper we investigate first passage percolation on an inhomogeneous random graph model introduced by Bollobás et al. (2007). Each vertex in the graph has a type from a type space, and edge probabilities are independent, but depend on the types of the end vertices. Each edge is given an independent exponential weight. We determine the distribution 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 the average number of neighbors $\tilde{\lambda}_n$ of a vertex tends to a finite $\tilde{\lambda}$ in full generality and consider $\tilde{\lambda}=\infty$ under mild assumptions. This paper is a generalization of the paper of Bhamidi et al. (2011), where first passage percolation is explored on the Erdos-Rényi graphs.
Originele taal-2Engels
Pagina's (van-tot)589-610
Aantal pagina's22
TijdschriftAdvances in Applied Probability
Nummer van het tijdschrift2
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'First passage percolation on inhomogeneous random graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit