The diameter of weighted random graphs

Abstract

In this paper we study the impact of random exponential edge weights on the distances in a random graph and, in particular, on its diameter. Our main result consists of a precise asymptotic expression for the maximal weight of the shortest weight paths between all vertices (the weighted diameter) of sparse random graphs, when the edge weights are i.i.d. exponential random variables.

Published at http://dx.doi.org/10.1214/14-AAP1034 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Distances in random graphs with finite variance degrees
• Asymptotic normality of the $k$-core in random graphs
• A simple solution to the k-core problem

Cited by in corpus (9)

• Robustness of football passing networks against continuous node and link removals
• First Passage Percolation on Inhomogeneous Random Graphs
• Shortest-weight paths in random regular graphs
• Probability-graphons: Limits of large dense weighted graphs
• Flooding and Diameter in General Weighted Random Graphs
• A practical Single Source Shortest Path algorithm for random directed graphs with arbitrary weight in expecting linear time
• First passage percolation in sparse random graphs with boundary weights
• The duration of an $SIR$ epidemic on a configuration model
• Far-out Vertices In Weighted Repeated Configuration Model